BOJ 11510 - TOPOVI (constructive, greedy)

https://www.acmicpc.net/problem/11510

시공간복잡도 파악이 힘들어서 풀이방법 자체가 떠오르지 않았다.

 

<문제설명>

최대 1e9*1e9 정사각형 모양의 한 변의 길이가 n인 그리드위에 룩(rook)을 배치할 것이다. 모든 룩은 1e9 이하의 power를 부여받는다.

 

power가 x인 룩이 (r,c)에 배치된다면, r번 row의 모든 칸의 값에 x를 XOR한 값을 저장한다. c번 column도 마찬가지다. (따라서 칸(r,c)는 두 번 xor되므로 칸(r,c)에 저장된 값은 변하지않는다.)

 

초기에 최대 1e5개의 룩 k개를 배치한다. (r,c,x)

이후에 최대 1e5번 (r1,c1)에 위치한 룩을 모두 (r2,c2)에 이동시킨다. (r1,c1,r2,c2 ,, 꼭 (r1,c1)에 룩이 있다는 보장은 없다.)

 

룩을 이동시킬 때마다 그리드 위의 0이 아닌 값의 개수를 구하여라.

 

<풀이>

power[{r,c}] : (r,c)에 위치한 모든 룩의 power xor .. 모든 룩을 하나하나 관리하지 않고 각 칸마다 power xor값 유지

rxor[r] : r번 row에 위치한 모든 룩의 xor값

ccnt[x] :  cxor[0]~cxor[n-1] 중 x값을 갖는 개수

sum : 그리드 위의 칸 중 0이 아닌 것의 개수

 

x를 갖는 룩이 '빈칸'(r,c)에 배치된다면 

rxor[r] ^= x;  rcnt[rxor[r]]++;

cxor[c] ^= x; ccnt[cxor[r]]++;

power[{r,c}] ^= x;

sum += r번 row와 c번 column 에서 켜지는 것의 개수 - ((r,c)가 0이 아니면 두번 빼주는것이므로 이것 고려한 값)

 

r번 row에서 켜지는 것의 개수는 column 중 rxor[r]의 값을 갖는 개수를 n에서 제외한 개수이다.

sum += n-ccnt[rxor[r]];

c번 column에 대해 마찬가지로,

sum += n-rcnt[cxor[c]];

 

 

더 나아가 x를 갖는 룩이 '비어있지 않은 칸' (r,c)에 배치된다면 이미 있는 값 power[{r,c}]을 가지고 한 번 xor해줘서 (r,c)를 빈 칸으로 만들어준다. 그 후 위와 같은 연산을 해주면 된다.

 

 

<코드>

int n, k, p;
ll sum;
map<int, int> rxor, cxor, rcnt, ccnt;
map<P, int> power;

void makeSum(int r, int c, int pw) {
	sum -= (n - ccnt[rxor[r]]); 
	sum -= (n - rcnt[cxor[c]]);
	if (rxor[r] != cxor[c]) sum++;

	rcnt[rxor[r]]--;
	ccnt[cxor[c]]--;

	rxor[r] ^= pw;
	cxor[c] ^= pw;
	power[{r, c}] ^= pw;
	ccnt[cxor[c]]++;
	rcnt[rxor[r]]++;

	sum += (n - ccnt[rxor[r]]);
	sum += (n - rcnt[cxor[c]]);
	if (rxor[r]!=cxor[c]) sum--;
}

int main() {
	FAST; cin >> n >> k >> p;
	rcnt[0] = ccnt[0] = n;
	for (int i = 0,r,c,x; i < k; i++) {
		cin >> r >> c >> x;
		r--; c--;
		makeSum(r, c, x);
	}

	for (int i = 0,r1,c1,r2,c2; i < p; i++) {
		cin >> r1 >> c1 >> r2 >> c2;
		r1--; c1--; r2--; c2--;
		int pw = power[{r1, c1}];
		makeSum(r1, c1, pw);
		makeSum(r2, c2, pw);
		cout << sum << '\n';
	}
}