2016年1月16日 星期六

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

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原