题目传送门(BZOJ)
>原文链接<

题解 :

维护一个支持插入, 排名区间查询, 修改, 查询排名的数据结构.

对于名字 : 我们可以使用map存一下, 或者你把它哈希了扔到一棵集合平衡树里, 或者哈希了扔到set里, 都是可行的方案, 当然map是最方便的啦.

对于插入, 我们就插入就好了

对于修改, 我们就修改就好了

设总人数是$sz$

对于查询排名, 我们把这个人拽到根, 它的排名就是$sz-siz[ls]-1$

对于查询排名区间$(x, y)$, 设$l = (sz-y-1), r = (sz-l-1)$ ,

把$l+2$拽到根, $r$拽到根的左儿子, 这样$r$的整棵左子树就是我们要的

注意$y$要和$sz$取$\min$.

都是一些基础的Splay操作, 就是最后那个操作不好调.

代码 :

#include <cstdio>#include <cstring>#include <algorithm>#include <map>#include <string>using namespace std;#define int long long map<string, int>id;map<int, string>nam;#define ls ch[p][0]#define rs ch[p][1]const int N = 251000;const int inf = 100000000000000;int ch[N][2], siz[N], f[N], root, cnt;long long val[N];#define get(x) (ch[f[x]][1]==x)inline void up(int p) { if(p) siz[p] = siz[ls]+siz[rs]+1;}void rotate(int x) { int y=f[x], z=f[y], k=get(x); ch[y][k] = ch[x][k^1]; f[ch[y][k]] = y; ch[x][k^1] = y; f[y]=x, f[x] = z; if(z) ch[z][ch[z][1]==y]=x; up(y), up(x); if(y==root) root=x;}void splay(int x, int y) { for(int fa;(fa=f[x])!=y;rotate(x)) { if(f[fa]!=y) rotate(get(x)==get(fa)?fa:x); }}void insert(int x, long long c) { int p = root; int l, r; while(p) { if(val[p]>=c) r=p, p=ls; else l=p, p=rs; } splay(l, 0);splay(r, root); ch[r][0] = x, f[x] = r;val[x] = c, siz[x] = 1;up(r), up(l);}void del(int x) { splay(x, 0); int l = ch[x][0], r=ch[x][1]; while(ch[l][1]) l =ch[l][1];while(ch[r][0])r=ch[r][0]; splay(l, 0); splay(r, root); ch[r][0]=0; f[x] = 0, siz[x] = 1; up(r), up(l);}void print(int p) { if(rs) print(rs); printf("%s ", nam[p].c_str()); if(ls) print(ls);}int find(int x) { int p =root; while(1) { if(x<=siz[ls])p=ls; else { x-=siz[ls]+1; if(!x) return p; p=rs; } }}void qrk(int l, int r) { l=cnt-l-1, r=cnt-r-1; swap(l, r); l=find(l), r=find(r+2); splay(l, 0); splay(r, root); print(ch[r][0]); puts("");}#undef intint main() {#define int long long int n; val[1] = -inf, val[2] = inf; ch[1][1] = 2;f[2] =1;root=1;siz[1]=2, siz[2] = 1;cnt=2; scanf("%lld", &n); while(n--) { char c = getchar(); while(c!='+'&&c!='?') c=getchar(); char name[20];long long num; scanf("%s", name); if(c=='+') { scanf("%lld", &num); if(id.count(name)) { int x = id[name]; del(x); insert(x, num); } else { cnt++; insert(cnt, num); id[name] = cnt; nam[cnt] = name; } } else { if(isdigit(name[0])) { int rk; sscanf(name, "%lld", &rk); qrk(rk, min(rk+9, cnt-2)); } else { int x = id[name]; splay(x, 0); printf("%lld\n", cnt-siz[ch[x][0]]-1); } } }}