[HOJ 299]比特集合

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

對於Insert、Delete、Add操作，只要先設定一個時間基準，假設是西元T年好了，然後每次Insert或Delete操作前先回推到西元T年時這隻小雞幾歲，然後在這個時間下作操作就好，Add的話就現在時間增加一年，實作上可以只用一個int變數來維護時間差
複雜度：使用map的話Insert和Delete都是O(log n(小雞))，Add是O(1)

相信大家會卡的應該是Q-bit操作
首先可以注意到Q-bit操作的d不會大於15，因此儲存數量級2^(d+1)的資料是可行的
想像一下，如果我們維護模2^(d+1)是v歲的小雞數量，假設是cnt[v]好了，把所有的cnt[v]都存下來，那麼答案就是Sum{cnt[v],v=2^d~2^(d+1)-1}了

於是乎問題轉換成動態求區間和了
因此我們可以考慮維護16個樹狀數組，第i個樹狀樹組維護的是d=i的情況下，所有cnt[v]的資訊，由於會有Add的操作，所以在對樹狀數組進行操作之前都要先轉換成西元T年的數據，算出對應的區間，Query其中的Sum就好
注意，區間有可能被切成兩段，視情況而定

時間複雜度每次操作不大於O(log n(小雞))

code:

#include<cstdio>
#include<map>
#include<vector>
#include<cassert>
using namespace std;
struct Bit
{
    vector<int>s;
    int n;
    Bit(){}
    Bit(const int _n):n(_n){s.clear(),s.resize(n+1,0);}
    void Add(int i,const int v)
    {
        i=(i%n+n)%n+1;
        while(i<=n)s[i]+=v,i+=(i&(-i));
    }
    int Query(int i)
    {
        assert(0<=i&&i<n);i++;
        int ans=0;
        while(i)ans+=s[i],i-=(i&(-i));
        return ans;
    }
    int QueryAns(int dis)
    {
        assert(dis>=0),dis%=n;
        if(dis<n/2)return Query(n-1-dis)-Query(n/2-dis-1);
        else return Query(n-1-dis)+(Query(n-1)-Query(n+n/2-dis-1));
    }
}BIT[16];
int N,ADD;
map<int,int>S;
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d",&N);
    ADD=0,S.clear();
    for(int i=0;i<=15;i++)BIT[i]=Bit(1<<(i+1));
    for(int i=0,val;i<N;i++)
    {
        static char tmp[7];
        scanf("%s%d",tmp,&val);
//        printf("%s %d\n",tmp,val);
        switch(tmp[0])
        {
            case'A':ADD+=val;break;
            case'D':
            {
                const auto it=S.find(val-ADD);
                if(it==S.end())break;
                for(int i=0;i<=15;i++)BIT[i].Add(val-ADD,-(it->second));
                S.erase(it);
            }break;
            case'I':
            {
                for(int i=0;i<=15;i++)BIT[i].Add(val-ADD,1);
                S[val-ADD]++;
            }break;
            case'Q':printf("%d\n",BIT[val].QueryAns(ADD));break;
            default:assert(0);break;
        }
    }
    return 0;
}