```c++
int SBT::find(int x,int c)
{
if(x==0)return 0;
if(c==tr[x].c)return tr[x].key;
else
{
if(c<tr[x].c)return find(tr[x].l,c);
else return find(tr[x].r,c);
}
}
int rank(int x)
{
if(x==A.root)return A.tr[A.tr[x].l].size+1;
if(A.tr[A.tr[x].f].l==x)
{
return rank(A.tr[x].f)-A.tr[A.tr[x].r].size-1;
}
else
{
return rank(A.tr[x].f)+A.tr[A.tr[x].l].size+1;
}
}
char* select(int x,int k)
{
if(k==A.tr[A.tr[x].l].size+1)return A.tr[x].s;
else
{
if(k<A.tr[A.tr[x].l].size+1)return select(A.tr[x].l,k);
else return select(A.tr[x].r,k-A.tr[A.tr[x].l].size-1);
}
}
const int base=129,mod=1000000009;
int hash(char s[])
{
int n=strlen(s);
long long hash=0;
for(int i=0;i<n;i++)
{
int c=s[i];
hash=(hash*base+c)%mod;
}
return int(hash);
}
char a[11];
inline int mymin(int x,int y){return x<y?x:y;}
int main()
{
int t;scanf("%d",&t);
for(int i=1;i<=t;i++)
{
char c=getchar();
while(c=='\n'||c=='\r'||c==' ')c=getchar();
if(c=='+')
{
scanf("%s",a);
int sc=0;read(sc,false);
int hh=hash(a);
int tt=B.find(B.root,hh);
if(tt==0)
{
A.add(A.root,sc,hh,a);
B.add(B.root,hh,A.len,a);
}
else
{
int rak=rank(tt);
del(A.root,rak);
B.del(B.root,hh);
A.add(A.root,sc,hh,a);
B.add(B.root,hh,A.len,a);
}
}
else
{
c=getchar();
if(c>='0'&&c<='9')
{
int rk=c-'0';
read(rk,true);
int g=mymin(rk+9,A.tr[A.root].size);
for(int i=rk;i<g;i++)
{
printf("%s ",select(A.root,A.tr[A.root].size-i+1));
}
printf("%s\n",select(A.root,A.tr[A.root].size-g+1));
}
else
{
int i=0;
a[i++]=c;
c=getchar();
while(c>='A'&&c<='Z'){a[i++]=c;c=getchar();}
a[i]='\0';
int hh=hash(a);
int tt=B.find(B.root,hh);
printf("%d\n",A.tr[A.root].size-rank(tt)+1);
}
}
}
return 0;
}
```
感觉代码不是一般的长啊啊啊啊啊
by zhoufangyuanPT @ 2018-05-10 19:28:26
终于AC了，耗费了整整一个版面
by zhoufangyuanPT @ 2018-05-15 21:23:53