题目传送门 题目大意： 看题面吧。
具体做法： hash+splay，数据结构题得自己看代码。
代码:
#include <bits/stdc++.h> using namespace std; const int maxn=1e6+10,mod=999983,inf=2147483647; int num[maxn],size[maxn],c[maxn][2],f[maxn],ans[maxn],h[maxn],sp; char name[maxn][20]; int root,cnt,n,p; void init() { c[1][1]=2,f[2]=1,size[1]=2,size[2]=1;root=1;cnt=2; num[1]=-inf,num[2]=inf; } void pushup(int x) { size[x]=size[c[x][0]]+size[c[x][1]]+1; } void rotate(int x) { int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k]; c[z][c[z][1]==y]=x,c[x][!k]=y,c[y][k]=w; f[w]=y,f[y]=x,f[x]=z; pushup(y);pushup(x); } void splay(int x,int tar) { while(f[x]!=tar) { int y=f[x],z=f[y]; if(z!=tar) rotate((c[y][1]==x)^(c[z][1]==y)?x:y); rotate(x); } if(tar==0) root=x; } void insert(int pos,int val) { int x=root,fa=0; while(x) { fa=x;x=c[x][val>num[x]]; } // printf("%d %d\n",x,fa); if(fa!=0) c[fa][val>num[fa]]=pos; size[pos]=1;num[pos]=val;c[pos][0]=c[pos][1]=0;f[pos]=fa;splay(pos,0); //printf("1\n"); } void erase(int x) { splay(x,0); if(!c[root][1]) { f[c[root][0]]=0; root=c[root][0]; } else { int y=c[root][1]; while(c[y][0]) y=c[y][0]; splay(y,root); c[y][0]=c[root][0]; f[c[root][0]]=y; f[y]=0; root=y; pushup(y); } } int hash(char *s) { int l=strlen(s),res=0; for(int i=0;i<l;i++) res=(res*27+(s[i]-'@'))%mod; return res; } int find(int num1) { int x=root; while(1) { if(num1<size[c[x][1]]+1) x=c[x][1]; else if(num1==size[c[x][1]]+1) return x; else { num1-=(size[c[x][1]]+1);x=c[x][0]; } } } void access(int x) { if(!x) return; access(c[x][1]); ans[++sp]=x; access(c[x][0]); } int rank(int x) { splay(x,0); return size[c[root][1]]; } int main() { scanf("%d",&n); init(); while(n--) { char kk,s[20]; kk=getchar(); while(kk!='+'&&kk!='?') kk=getchar(); if(kk=='+') { // printf("%d\n",root); scanf("%s%d",s,&p); int t=hash(s),pos=0; // cout<<t<<endl; while(1) { if(!h[t]) { pos=t;break; } else if(!strcmp(name[h[t]],s)) { pos=t;break; } else { t++; if(t==mod+1) t=1; } } // cout<<pos<<endl; if(!h[pos]) { // cout<<1<<endl; h[pos]=++cnt; // cout<<cnt<<endl; memcpy(name[cnt],s,strlen(s)); // cout<<1<<endl; insert(cnt,p); } else { erase(h[pos]); insert(h[pos],p); } // cout<<1<<endl; } else { scanf("%s",s); if(s[0]>='0'&&s[0]<='9') { sscanf(s,"%d",&p); int x=p+1,y=min(p+10,size[root]-1); x=find(x-1);y=find(y+1); swap(x,y); splay(x,0);splay(y,root); sp=0; access(c[c[root][1]][0]); for(int i=1;i<=sp;i++) printf("%s ",name[ans[i]]); printf("\n"); } else { int t=hash(s); // cout<<t<<endl; while(1) { if(!strcmp(s,name[h[t]])) { printf("%d\n",rank(h[t]));break; } else { t++; if(t==mod+1) t=1; } } } } } return 0; }