题目链接: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;
}