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