AOJ 2615: A + B

Bのうち最上位にある1の位置をat(0-origin)とすると
「atの場所は0」「at未満のところを好き放題いじる」という値はBより小さく、この値をCとすると
A+Cは「(Aのat以上のbitの1の個数)+at」個の1がある。
これより大きくすることができることもある。ただしこれは「atの場所を1にしてそれ以下も全部1にできる」というケースだけ考えればよくて、このケースが達成できる条件は、
・Aのat番目のbitが0
・at番目以下でA,Bのbit両方が1となる箇所が両方0となる箇所より先に出てくる
ということである。

あとはこの条件をsetとBITで実装する。

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
using namespace std;
char A[310000];
char B[310000];
int p[310000];
int q[310000];
int bit[310000];
set<int>zero;
set<int>two;
set<int>bb;
int sum(int a,int b){
	if(a)return sum(0,b)-sum(0,a-1);
	int ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[b];
	return ret;
}
void add(int a,int b){
	for(;a<310000;a|=a+1)bit[a]+=b;
}
char in[2];
int main(){
	int a;
	scanf("%d",&a);
	scanf("%s%s",A,B);
	int as=strlen(A);
	int bs=strlen(B);
	two.insert(-1);
	zero.insert(-1);
	for(int i=0;i<as;i++){
		p[i]=A[as-1-i]-'0';
	}
	for(int i=0;i<bs;i++){
		q[i]=B[bs-1-i]-'0';
	}
	int sz=max(as,bs)+1;
	for(int i=0;i<sz;i++){
		if(p[i]+q[i]==2)two.insert(i);
		if(p[i]+q[i]==0)zero.insert(i);
		if(q[i])bb.insert(i);
		if(p[i])add(i,1);
	}
	for(int i=0;i<a;i++){
		scanf("%s",in);
		if(in[0]=='Q'){
			int at=*(bb.rbegin());
			int val=sum(at,sz);
			int ret=val+at;
			if(p[at]==0){
				int nt=*(--(two.lower_bound(at)));
				int nz=*(--(zero.lower_bound(at)));
		//		printf("%d %d\n",nt,nz);
				if(nt>nz){
					ret++;
				}
			}
			printf("%d\n",ret);
		}else if(in[0]=='A'){
			int t;scanf("%d",&t);
			if(p[t]==0){
				if(q[t]+p[t]==0)zero.erase(t);
				p[t]=1;
				if(q[t]+p[t]==2)two.insert(t);
				add(t,1);
			}else{
				if(q[t]+p[t]==2)two.erase(t);
				p[t]=0;
				if(q[t]+p[t]==0)zero.insert(t);
				add(t,-1);
			}
		}else{
			int t;scanf("%d",&t);
			if(q[t]==0){
				if(q[t]+p[t]==0)zero.erase(t);
				q[t]=1;
				if(q[t]+p[t]==2)two.insert(t);
				bb.insert(t);
			}else{
				if(q[t]+p[t]==2)two.erase(t);
				q[t]=0;
				if(q[t]+p[t]==0)zero.insert(t);
				bb.erase(t);
			}
		}
	}
}