またゴリ押し。
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にするメンバ関数作ってくれないかな…。