一時期SRMでもこんな問題でたなぁ。
https://csacademy.com/contest/round-32/task/light-count/
問題
1~Nの番号の電球が並んでいる。
以下のクエリM個に答えよ。
- k番の電球のオンオフを切り替える。
- [L,R]番の範囲の電球でオンのものの数を数え上げる。
ただしN≦5*10^7、M≦2*10^7の制限に対しメモリは12MBしか使えない。
解法
オンオフは1電球1bitで管理すればメモリに収まる。
数え上げはBITで行えばよいが、普通に行うとMLEする。
以下のコードでは電球1024個ごとにカウンタを持ち、BITを用いた。
カウンタをまとめるサイズをBとすると、1クエリO(B+log(N/B))で処理でき何とか間に合う。
unsigned long long B[50000000/64+1]; template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;} }; BIT<int,17> bt; struct RandGen { int x, y, z; int nextInt() { int t = x ^ (x << 11); x = y; y = z; z ^= (z >> 19) ^ t ^ (t >> 8); return z; } int random(int N) { return nextInt() % N; } }; void init(int N, int M) { } void flipPosition(int poz) { unsigned long long m=1ULL<<(poz&63); if(B[poz>>6] & m) { bt.add((poz>>10)+1,-1); } else { bt.add((poz>>10)+1,+1); } B[poz>>6] ^= m; } int getCount(int st, int fn) { int ret=0; if(fn-st<=128) { while(st<=fn) { if(B[st>>6]&(1ULL<<(st&63))) ret++; st++; } } else { while(st&63) { if(B[st>>6]&(1ULL<<(st&63))) ret++; st++; } while((fn&63)!=63) { if(B[fn>>6]&(1ULL<<(fn&63))) ret++; fn--; } if(fn-st<=2048) { while(st<=fn) { ret+=__builtin_popcountll(B[st>>6]); st+=64; } } else { while(st&1023) { ret+=__builtin_popcountll(B[st>>6]); st+=64; } while((fn&1023)!=1023) { ret+=__builtin_popcountll(B[fn>>6]); fn-=64; } if(st<fn) ret+=bt((fn+1)>>10)-bt((st>>10)); } } return ret; } int main() { int N, M; RandGen rng; cin >> N >> M >> rng.x >> rng.y >> rng.z; init(N, M); long long hashSol = 0; for (long long i = 0; i < M; i++) { if (rng.random(2) == 0) { const int poz = rng.random(N); flipPosition(poz); } else { int st = rng.random(N), fn = rng.random(N); if (st > fn) { swap(st, fn); } hashSol ^= i * getCount(st, fn); } } cout << hashSol << "\n"; }
まとめ
何がしたかったんだろう。