后七个点全T了,是我splay的姿势不对么(
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char Name[500][15];int n,m,q;
struct S_Play{
int siz[100005],f[100005],ch[2][100005],tot=0,rot=1;
char name[100005][15];
inline void push_up(int x){siz[x]=siz[ch[0][x]]+siz[ch[1][x]]+1;}
inline void rotate(int x){
int y=f[x],z=f[y],k=ch[1][y]==x;
f[x]=z;ch[ch[1][z]==y][z]=x;
f[ch[k^1][x]]=y;ch[k][y]=ch[k^1][x];
f[y]=x;ch[k^1][x]=y;
push_up(y);push_up(x);
}
inline void splay(int x,int goal){
while(f[x]!=goal){
int y=f[x],z=f[y];
if(z!=goal)
((ch[1][y]==x)^(ch[1][z]==y))?rotate(x):rotate(y);
rotate(x);
}
if(goal==0)rot=x;
}
int build(int l,int r,int pre){
if(l>r)return 0;
int mid=l+r>>1,u=++tot,g=0;
while(Name[mid][g]){name[u][g]=Name[mid][g];g++;}f[u]=pre;
ch[0][u]=build(l,mid-1,u);
ch[1][u]=build(mid+1,r,u);
push_up(u);
return u;
}
inline int kth(int k){
int u=rot;
while(1){
if(siz[ch[0][u]]>=k)u=ch[0][u];
else{
k-=siz[ch[0][u]];
if(k==1)return u;
k--;u=ch[1][u];
}
}
}
inline void insert(int k,char s[15]){
int x=kth(k-1),y=kth(k);
splay(x,0);splay(y,x);
int u=++tot;
ch[0][y]=u;
for(int g=0;s[g];g++)name[u][g]=s[g];
siz[u]=1;f[u]=y;
splay(u,0);
}
inline void print(int x){
if(ch[0][x])print(ch[0][x]);
printf("%s ",name[x]);
if(ch[1][x])print(ch[1][x]);
}
}t;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%s",Name[i+1]);
t.build(1,n+2,0);
scanf("%d",&m);
while(m--){
int k;char s[15];
scanf("%s %d",s,&k);
t.insert(min(k+2,t.tot),s);
}
scanf("%d",&q);
while(q--){
int k;
scanf("%d",&k);
printf("%s\n",t.name[t.kth(k+2)]);
}
return 0;
}