kmjp's blog

競技プログラミング参加記です

Codeforces ECR #023: F. MEX Queries

またゴリ押し。
http://codeforces.com/contest/817/problem/F

問題

整数集合Sに対し、以下のクエリを順次処理し、その後Sに含まれない最小の正整数を求めよ。

  • S中に[L,R]の範囲の整数を追加する
  • S中にある[L,R]の範囲の整数を削除する
  • S中にある[L,R]の範囲の整数を追加/削除反転する

解法

まず登場する整数群を座標圧縮しておこう。
あとは遅延伝搬SegTreeで各クエリを処理することもできるが、Sにあるなしの2値を管理すればいいのでbitset(もどき)でビット演算すればO(Q^2/W)でゴリ押せる。

int N;
int T[101010];
ll L[101010],R[101010];
vector<ll> VP;
unsigned long long hoge[205020/64];
unsigned long long BS[205020/64];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	VP.push_back(1);
	FOR(i,N) {
		cin>>T[i]>>L[i]>>R[i];
		VP.push_back(L[i]);
		VP.push_back(R[i]+1);
	}
	sort(ALL(VP));
	VP.erase(unique(ALL(VP)),VP.end());
	FOR(i,202020/64+2) hoge[i]=~0ULL;
	
	FOR(i,N) {
		int LL=lower_bound(ALL(VP),L[i])-VP.begin();
		int RR=lower_bound(ALL(VP),R[i]+1)-VP.begin();
		ZERO(BS);
		while((LL&63)&&LL<RR) BS[LL>>6] |= 1ULL<<(LL&63), LL++;
		while((RR&63)&&LL<RR) RR--, BS[RR>>6] |= 1ULL<<(RR&63);
		while(LL<RR) BS[LL>>6]=~0ULL, LL+=64;
		if(T[i]==1) {
			FOR(x,VP.size()/64+2) hoge[x] &= ~BS[x];
		}
		if(T[i]==2) {
			FOR(x,VP.size()/64+2) hoge[x] |= BS[x];
		}
		if(T[i]==3) {
			FOR(x,VP.size()/64+2) hoge[x] ^= BS[x];
		}
		FOR(x,VP.size()/64+2) if(hoge[x]) {
			FOR(j,64) if(hoge[x]&(1ULL<<j)) {
				cout<<VP[x*64+j]<<endl;
				break;
			}
			if(j<64) break;
		}
	}
}

まとめ

いや、本番SegTreeも思いついたけど面倒でね。
STLのbitset、指定した範囲を1にするメンバ関数作ってくれないかな…。