[bzoj1273] [BeiJingWc2008]序列

　　一开始想拆位。。但显然没法应对进位啊什么的。

　　所以维护每一个长度的后缀。

　　查询有多少个a&2^i>0，也就是长度为(i+1)的后缀里，值为2^i…2^(i+1)-1的数有多少个。

　　前缀和一波就好了。。整体加就开个变量记着，查询的时候再分一下类。

 #include<cstdio>
 #include<iostream>
 #include<cstring>
 #define ll long long
 using namespace std;
 const int maxn=;
 int sm[][<<|],a[maxn];
 int add[],one[];
 int i,j,k,n,m,L,R,SM;
 ll ans; int ra;char rx;
 inline int read(){
     rx=getchar(),ra=;
     while(rx<''||rx>'')rx=getchar();
     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
 }
 int main(){
     n=read(),m=read();register int j;
     for(i=;i<=n;i++)a[i]=read();
     for(i=;i<=;i++)one[i]=one[i-]<<|;
     for(i=;i<=;i++){
         for(j=;j<=n;j++)sm[i][a[j]&one[i]]++;
         for(j=;j<=one[i];j++)sm[i][j]+=sm[i][j-];
     }char s[];int x;
     while(m--){
         scanf("%s",s);x=read();
         if(s[]=='A')for(i=;i<=;i++)add[i]+=x&one[i],add[i]&=one[i];
         else
             x++,L=(<<(x-))-add[x],R=one[x]-add[x],SM=,
             ans+=L>=?(sm[x][R]-(!L?:sm[x][L-])):(sm[x][R]+sm[x][one[x]]-sm[x][L+(<<x)-]);
     }
     printf("%lld\n",ans);
 }