CodeForces 916D Jamie and To-do List (主席樹+map)

題目連結:http://codeforces.com/problemset/problem/916/D

題目大意

給定四種操作，

第一種：設定字元串的優先級，若該字元串事先沒有出現過，

則添加上去，否則修改。

第二種：删除操作，删除指定的字元串

第三種：傳回操作，回退k個操作，

第四種：查詢指定字元串，其有多少個字元串的優先級小于它。

題目分析 

看到時間回退操作不難想到可持久化，

但是其對象是字元串，那麼我們再建立一層映射（hash好像不太穩。。。）

我們通過map把字元串搞成下标數字，然後維護兩個線段樹根數組，

第一個是代表i優先級有多少個字元串，第二個代表下标數字i對應的優先級是多少。

那麼因為x的範圍是九次方，是以對區間1到1e9建樹，數組大小注意下。

那麼對于傳回操作，我們隻要把目前兩個根節點指派過去的根節點即可，

我們下一次就可以依賴過去的狀态來更新現在了。

關于查詢，删除，和設定操作，一般流程就是先到map裡面找字元串下标，

找不到則表明是新的串，但是可以保證其傳回下标一定沒有被指派，

那麼對于給定的下标我們到第二種樹中查詢其優先級，然後根據這個

修改第一種樹的數量，這三種 操作其本質也差不多，

set操作要考慮消去過去的影響，寫好了更新和查詢的模闆這些都不複雜。

#include<bits/stdc++.h>
using namespace std;

#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long

#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=2e5+5;
const int maxm=1e7+5;
const int ub=1e6;
const int INF=1e9;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
題目大意：
給定四種操作，
第一種：設定字元串的優先級，若該字元串事先沒有出現過，
則添加上去，否則修改。
第二種：删除操作，删除指定的字元串
第三種：傳回操作，回退k個操作，
第四種：查詢指定字元串，其有多少個字元串的優先級小于它。

題目分析：
看到時間回退操作不難想到可持久化，
但是其對象是字元串，那麼我們再建立一層映射（hash好像不太穩。。。）
我們通過map把字元串搞成下标數字，然後維護兩個線段樹根數組，
第一個是代表i優先級有多少個字元串，第二個代表下标數字i對應的優先級是多少。
那麼因為x的範圍是九次方，是以對區間1到1e9建樹，數組大小注意下。
那麼對于傳回操作，我們隻要把目前兩個根節點指派過去的根節點即可，
我們下一次就可以依賴過去的狀态來更新現在了。
關于查詢，删除，和設定操作，一般流程就是先到map裡面找字元串下标，
找不到則表明是新的串，但是可以保證其傳回下标一定沒有被指派，
那麼對于給定的下标我們到第二種樹中查詢其優先級，然後根據這個
修改第一種樹的數量，這三種 操作其本質也差不多，
set操作要考慮消去過去的影響，寫好了更新和查詢的模闆這些都不複雜。

*/
string s;
int n,x,y;
map<string,int> mp;
int rt1[maxn],rt2[maxn];///每個等級對應的字元串個數，每個id的占用情況
int ls[maxm],rs[maxm],sum[maxm];
int id=0,tot=0;
void update(int &o,int last,int l,int r,int p,int v){
    o=++tot;
    ls[o]=ls[last],rs[o]=rs[last];
    sum[o]=sum[last]+v;
    if(l==r) return ;
    int mid=l+r>>1;
    if(p<=mid) update(ls[o],ls[last],l,mid,p,v);
    else update(rs[o],rs[last],mid+1,r,p,v);
}
int query(int o,int l,int r,int pl,int pr){
    if(pl>pr) return 0;
    if(pl<=l&&r<=pr) return sum[o];
    int mid=l+r>>1,ans=0;
    if(pl<=mid) ans+=query(ls[o],l,mid,pl,pr);
    if(mid<pr) ans+=query(rs[o],mid+1,r,pl,pr);
    return ans;
}
int getid(string p){
    if(mp.count(p)) return mp[p];
    else return mp[p]=++id;
}
int main(){
    cin>>n;
    rep(i,1,n+1){
        rt1[i]=rt1[i-1],rt2[i]=rt2[i-1];
        cin>>s;
        if(s[0]=='s'){
            cin>>s>>x;
            int idx=getid(s);
            int ret=query(rt2[i],1,INF,idx,idx);
            if(ret) update(rt1[i],rt1[i],1,INF,ret,-1);
            ///cout<<ret<<endl;
            update(rt1[i],rt1[i],1,INF,x,1);
            update(rt2[i],rt2[i],1,INF,idx,x-ret);
        }
        else if(s[0]=='q'){
            cin>>s;
            int idx=getid(s);
            int ret=query(rt2[i],1,INF,idx,idx);
            if(ret==0) puts("-1");
            else printf("%d\n",query(rt1[i],1,INF,1,ret-1));
            fflush(stdout);
        }
        else if(s[0]=='u'){
            cin>>x;
            rt1[i]=rt1[i-x-1];
            rt2[i]=rt2[i-x-1];
        }
        else{///删除這個字元串
            cin>>s;
            int idx=getid(s);
            int ret=query(rt2[i],1,INF,idx,idx);///
            if(ret==0) continue;
            update(rt1[i],rt1[i],1,INF,ret,-1);
            update(rt2[i],rt2[i],1,INF,idx,-ret);
        }
    }
    return 0;
}