BOJ 11833 돌 무게 재기

문제 링크입니다.

문제 요약

무게에 따른 오름차순으로 정렬된 $N$개의 돌이 주어집니다. 각 돌의 무게는 모두 서로 다르지만, 정확한 무게는 알 수 없습니다. 양팔저울에 돌을 올려놓는 쿼리가 누적해서 주어질 때, 각 상황마다 양팔저울이 어느 쪽으로 기울지 맞히거나, 알 수 없음을 밝히세요.

풀이

각 돌의 정확한 무게를 알 수 없기 때문에, 돌의 종류 별 개수를 통해 비교해야 합니다. 예를 들어 모든 종류의 돌이 왼쪽보다 오른쪽에 더 많으면 저울은 당연히 오른쪽으로 기울겠죠.

문제는 이렇게 하면 왼쪽에 1번 돌이 있고 오른쪽에 2번 돌이 있는 경우를 판정할 수 없게 됩니다. 그래서 정확히는, 한쪽의 돌을 다른 쪽의 더 무거운 돌과 매칭할 수 있는지 판정해야 합니다. 여기서 괄호 문자열 내지는 산 그림 같은 걸 떠올린 다음에 그에 맞는 적당한 세그를 떠올리면 문제를 풀 수 있습니다. 아래는 제가 2년 전에 풀었던 접근 방식입니다.

각 돌의 무게를 $W_1 , W_2 , \cdots , W_N$이라고 합시다. $N$번째 돌을 $N$개의 조각으로 분할합니다. 첫 번째 조각의 무게는 $W_1$, 두 번째 조각의 무게는 $W_2 - W_1$, … , $N$번째 조각의 무게는 $W_N - W_{N-1}$입니다. 돌의 무게가 모두 다르므로 이 값은 모두 양수입니다. 이를 각 돌마다 반복하면, 각 조각 별 개수를 비교해서 돌의 무게가 서로 다를 때에도 판정이 가능해집니다. 레이지 없이 처리할 수 있긴 한데 생각하기 귀찮으니까 그냥 레이지 세그로 구간에 1 또는 -1씩 뿌려주면서 최댓값/최솟값을 관리해 주면 문제를 해결할 수 있습니다.

총 시간 복잡도는 ${\cal O}(N \lg N)$입니다.

코드

#include <bits/stdc++.h>
using namespace std;
int seg[2][456789], lazy[456789];
 
void prop(int now, int l, int r){
	if(lazy[now]){
		if(l != r){
			lazy[now<<1] += lazy[now];
			lazy[now<<1|1] += lazy[now];
		}
		seg[0][now] += lazy[now];
		seg[1][now] += lazy[now];
		lazy[now] = 0;
	}
}

void upd(int now, int l, int r, int L, int R, int k){
	prop(now, l, r);
	if(r < L || l > R) return;
	if(L <= l && r <= R){
		lazy[now] += k;
		prop(now, l, r);
		return;
	}
	int mid = (l + r)>>1;
	upd(now<<1, l, mid, L, R, k);
	upd(now<<1|1, mid+1, r, L, R, k);
	seg[0][now] = max(seg[0][now<<1], seg[0][now<<1|1]);
	seg[1][now] = min(seg[1][now<<1], seg[1][now<<1|1]);
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n;
	for(int i = 0; i < n; i++){
		int r, s; cin >> r >> s;
		if(s == 1) upd(1, 1, n, 1, r, 1);
		else upd(1, 1, n, 1, r, -1);
		if(seg[1][1] >= 0) cout << ">\n";
		else if(seg[0][1] <= 0) cout << "<\n";
		else cout << "?\n";
	}
}