BZOJ2568 比特集合（树状数组）

　　考虑维护f[k][x]表示“最低k位所表示的数不大于x”的数的个数。那么查询时答案就为f[k][2^k-1]-f[k][2^k-1-1]。

　　同时记录每个数在集合中出现多少次。这样的话插入、删除已经解决了，只剩下加操作。考虑对每一个k都将加操作带来的影响累计作为偏移量就可以了。

　　明明不知道在写什么结果1A有点爽啊。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
#define K 16
int q,d,tree[K][1<<K],delta[K];
map<int,int> cnt;
void add(int k,int x,int p){if (x==0) tree[k][0]+=p,x=1;while (x<(2<<k)) {tree[k][x]+=p,x+=x&-x;}}
int query(int k,int x){if (x==0) return tree[k][0];int s=0;while (x) {s+=tree[k][x],x-=x&-x;}return s;}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("bzoj2568.in","r",stdin);
    freopen("bzoj2568.out","w",stdout);
    const char LL[]="%I64d
";
#else
    const char LL[]="%lld
";
#endif
    q=read();
    while (q--)
    {
        char c=getchar();
        while (c<'A'||c>'Z') c=getchar();
        int x=read();
        switch (c)
        {
            case 'A':
            {
                d+=x;
                for (int i=0;i<16;i++) delta[i]=(delta[i]+x)&(2<<i)-1;
                break;
            }
            case 'D':
            {
                x-=d;int y=cnt[x];
                for (int i=0;i<16;i++) add(i,x&(2<<i)-1,-y);
                cnt[x]=0;
                break;
            }
            case 'I':
            {
                x-=d;
                cnt[x]++;
                for (int i=0;i<16;i++) add(i,x&(2<<i)-1,1);
                break;
            }
            case 'Q':
            {
                int k=x;
                if (delta[k]<(1<<k)) printf("%d
",query(k,(2<<k)-1-delta[k])-query(k,(1<<k)-1-delta[k]));
                else printf("%d
",query(k,(2<<k)-1)-query(k,(1<<k)-1-delta[k]+(2<<k))+query(k,(2<<k)-1-delta[k]));
            }
        }
    }
    return 0;
}