Codeforces ECR #023 : E. Choosing The Commander

手抜きしちゃいかんね…。
http://codeforces.com/contest/817/problem/E

問題

隊の指揮官の性格をPc,リーダーシップをLとする。
性格がPsである兵士は、Ps xor Pc ＜ Lの時指揮官とウマがあう。

以下のクエリに順次答えよ。

• 性格がPsの兵士を隊に加える
• 性格がPsの兵士を隊から1名除隊する
• 性格Pc、リーダーシップLの指揮官がこの隊を指揮するとき、ウマがあう兵士の数を答える。

解法

登場する兵隊の性格を上のBitから見ていき二分木を構築し、SubTree内で現状隊にいる兵士の数の総和を持つようにしよう。
あとは指揮官のクエリに対し、二分木を上のビットに対応する頂点探索し、Ps xor Pc　＜ LになるSubTree内の兵士の総和を数え上げればよい。

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;
		}
	}
}

まとめ

最初手を抜いてO(Q^2)のコード書いたらやっぱりダメだった。