本文共 2592 字，大约阅读时间需要 8 分钟。
分析：
平衡树裸题，（学完LCT感觉自己不会普通的Splay了...），维护每个节点的权值大小顺序，和时间戳顺序，之后map维护一下是否存在过，（懒得写字符串hash了）。
附上代码：
#include #include #include #include #include #include #include #include using namespace std;#define N 300055#define ls ch[rt][0]#define rs ch[rt][1]#define get(rt) (ch[f[rt]][0]!=rt)int ch[N][2],f[N],siz[N],val[N],rot,cnt,n;map mp1;map mp2;char s[205];void PushUp(int rt){siz[rt]=siz[ls]+siz[rs]+1;}void rotate(int rt){ int x=f[rt],y=f[x],k=get(rt); ch[x][k]=ch[rt][!k];f[ch[x][k]]=x; ch[rt][!k]=x;f[x]=rt;f[rt]=y; if(x!=rot)ch[y][ch[y][0]!=x]=rt; PushUp(x);PushUp(rt);if(x==rot)rot=rt;}void Splay(int rt,int y){ for(int fa;(fa=f[rt])!=y;rotate(rt)) if(f[fa]!=y) rotate((get(rt)==get(fa))?fa:rt);}void insert(int v,int x){ int l,r,rt=rot; while(rt){if(val[rt]>=v)r=rt,rt=ls;else l=rt,rt=rs;} Splay(l,0);Splay(r,rot);ch[r][0]=x;f[x]=r,val[x]=v,siz[x]=1;PushUp(r);PushUp(l);}void del(int rt){ Splay(rt,0); int l=ch[rt][0],r=ch[rt][1];while(ch[l][1])l=ch[l][1];while(ch[r][0])r=ch[r][0]; Splay(l,0);Splay(r,rot);ch[r][0]=0;f[rt]=0;siz[rt]=0;PushUp(r);PushUp(l);}int find(int x){int rt=rot;while(1){if(siz[ls]>=x)rt=ls;else{x-=siz[ls]+1;if(!x)return rt;rt=rs;}}}int get_rank(int rt){Splay(rt,0);return siz[ls];}void print(int rt){ if(rs)print(rs); printf("%s ",mp2[rt].c_str()); if(ls)print(ls);}void out_put(int x,int y){ x=cnt-x-1;y=cnt-y-1;swap(x,y); //printf("%d %d\n",x,y); x=find(x),y=find(y+2);Splay(x,0);Splay(y,rot);print(ch[y][0]);}int main(){ char opt1=getchar(); while(opt1>='0'&&opt1<='9')n=((n<<3)+(n<<1))+opt1-'0',opt1=getchar(); val[1]=-1<<30;val[2]=2147483647;ch[1][1]=2;f[2]=1;rot=1;siz[1]=2;siz[2]=1;cnt=2; while(n--) { memset(s,0,sizeof(s)); int num=0,x=0; opt1=getchar();while(opt1!='+'&&opt1!='?') opt1=getchar(); if(opt1=='+') { opt1=getchar(); while(opt1>='A'&&opt1<='Z')s[num++]=opt1,opt1=getchar(); opt1=getchar(); while(opt1<'0'||opt1>'9')opt1=getchar(); while(opt1>='0'&&opt1<='9')x=((x<<3)+(x<<1))+opt1-'0',opt1=getchar(); //printf("%d\n",mp1.count(s)); if(mp1.count(s)) { int y=mp1[s]; del(y); insert(x,y); }else { cnt++;insert(x,cnt);mp1[s]=cnt;mp2[cnt]=s; //printf("%d\n",cnt); } }else { opt1=getchar(); if(opt1>='0'&&opt1<='9') { while(opt1>='0'&&opt1<='9')x=((x<<3)+(x<<1))+opt1-'0',opt1=getchar(); out_put(x,min(x+9,cnt-2)); puts(""); }else { while(opt1>='A'&&opt1<='Z')s[num++]=opt1,opt1=getchar(); //Splay(5,0);printf("%d\n",siz[5]); printf("%d\n",cnt-get_rank(mp1[s])-1); } } } return 0;}
转载于:https://www.cnblogs.com/Winniechen/p/9144126.html