BOJ 28742 Свадьба

문제 링크입니다.

문제 요약

세 가지 쿼리를 처리합니다.

• 수열에 $x$가 추가됩니다.
• 수열에 $i$번째로 추가된 원소를 제거합니다.
• 수열의 모든 원소에 $x$를 XOR합니다.

각 쿼리 후에 수열의 원소들의 합을 구하세요.

풀이

수열의 원소를 비트 단위로 쪼개서, 각 비트가 1인 것의 개수를 세 줍니다. 1, 2번 쿼리를 각각 $O(\lg maxA)$에 할 수 있습니다.

비트 단위로 쪼갠 이유는 3번 쿼리를 쉽게 처리하기 위함입니다. 수열 전역에 작용하는 XOR 오프셋을 도입해, 3번 쿼리를 단순히 오프셋을 바꾸는 것으로 처리해서 넘겨줍니다. 이후에 합을 계산할 때, 비트 별로 오프셋이 1이면 0인 원소 개수, 0이면 1인 원소 개수를 구해 주면 되니 매 쿼리가 끝난 뒤에 합 역시 $O(\lg maxA)$에 처리할 수 있습니다.

풀이가 올바르게 작동하기 위해서는 1번 쿼리에서 원소를 추가할 때 수열에 걸려 있는 XOR 오프셋을 적용해 주어야 함에 유의합시다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int a[202020], n, ptr;
ll cnt[32], x;

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int q; cin >> n >> q; ptr = n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		for(int bit = 0; bit <= 30; bit++) if(a[i]&(1<<bit)) cnt[bit]++;
	}
	while(q--){
		int op; cin >> op;
		if(op == 1){
			cin >> a[++ptr]; n++; a[ptr] ^= x;
			for(int bit = 0; bit <= 30; bit++) if(a[ptr]&(1<<bit)) cnt[bit]++;
		}else if(op == 2){
			int i; cin >> i; n--;
			for(int bit = 0; bit <= 30; bit++) if(a[i]&(1<<bit)) cnt[bit]--;
		}else{
			ll t; cin >> t; x ^= t;
		}
		ll ans = 0; for(int bit = 0; bit <= 30; bit++){
			if(x&(1LL<<bit)) ans += (n-cnt[bit])<<bit;
			else ans += cnt[bit]<<bit;
		}
		cout << ans << '\n';
	}
}