1 {$inline on}  2 const maxn=250000+100;inf=maxlongint;  3 var s,fa,v,next:array[0..maxn] of longint;  4     ss:array[0..maxn] of string[15];  5     head:array[0..1000000] of longint;  6     c:array[0..maxn,0..1] of longint;  7     i,j,n,x,y,rank,rt,tot,cnt:longint;  8     st,name:ansistring;  9     first:boolean; 10     ch:char; 11 function hash(s:ansistring):int64;inline; 12  var i,x:longint; 13  begin 14    x:=0; 15    for i:=1 to length(s) do x:=(x*131+ord(s[i])-ord(‘A‘)+1) mod 999983; 16    i:=head[x]; 17    while i<>0 do 18      begin 19       if ss[i]=s then exit(i); 20       i:=next[i]; 21      end; 22    inc(tot);ss[tot]:=s;v[tot]:=y;next[tot]:=head[x];head[x]:=tot; 23    exit(0); 24  end; 25 procedure pushup(x:longint);inline; 26  begin 27    s[x]:=s[c[x,0]]+s[c[x,1]]+1; 28  end; 29  30 procedure rotate(x:longint;var k:longint);inline; 31  var y,z,l,r:longint; 32  begin 33    y:=fa[x];z:=fa[y]; 34    l:=ord(c[y,1]=x);r:=l xor 1; 35    if y=k then k:=x else c[z,ord(c[z,1]=y)]:=x; 36    fa[x]:=z;fa[y]:=x;fa[c[x,r]]:=y; 37    c[y,l]:=c[x,r];c[x,r]:=y; 38    pushup(y);pushup(x); 39  end; 40 procedure splay(x:longint;var k:longint);inline; 41  var y,z:longint; 42  begin 43    while x<>k do 44     begin 45       y:=fa[x];z:=fa[y]; 46       if y<>k then 47         if (c[z,0]=y) xor (c[y,0]=x) then rotate(x,k) 48         else rotate(y,k); 49       rotate(x,k); 50     end; 51  end; 52 function find(x,rank:longint):longint;inline; 53  var l,r:longint; 54  begin 55    l:=c[x,0];r:=c[x,1]; 56    if s[l]+1=rank then exit(x) 57    else if s[l]>=rank then exit(find(l,rank)) 58    else exit(find(r,rank-s[l]-1)); 59  end; 60 procedure insert(var x:longint;f,k:longint);inline; 61  begin 62    if x=0 then 63      begin 64        fa[k]:=f; 65        x:=k; 66        s[k]:=1; 67        c[k,0]:=0;c[k,1]:=0; 68        exit; 69      end; 70    inc(s[x]); 71    if v[k]>v[x] then insert(c[x,0],x,k) else insert(c[x,1],x,k); 72  end; 73 procedure del(rank:longint);inline; 74  var x,y,z:longint; 75  begin 76    x:=find(rt,rank-1);y:=find(rt,rank+1); 77    splay(x,rt);splay(y,c[x,1]); 78    z:=c[y,0];fa[z]:=0;c[y,0]:=0;s[z]:=0; 79    pushup(y);pushup(x); 80  end; 81 procedure print(x:longint);inline; 82  begin 83  if x=0 then exit; 84  print(c[x,0]); 85  if first then begin first:=false;write(ss[x]);end else write(‘ ‘,ss[x]); 86  print(c[x,1]); 87  end; 88  89 procedure main; 90  begin 91    readln(n); 92    rt:=n+1;fa[n+1]:=0;v[n+1]:=-inf;v[n+2]:=inf; 93    insert(rt,0,n+2); 94    tot:=0; 95    for j:=1 to n do 96     begin 97       read(ch); 98       case ch of 99       ‘+‘:begin100           readln(st);101           name:=copy(st,1,pos(‘ ‘,st)-1);102           delete(st,1,pos(‘ ‘,st));103           val(st,y);104           x:=hash(name);105           if x=0 then insert(rt,0,tot)106           else107             begin108              splay(x,rt);del(s[c[rt,0]]+1);109              v[x]:=y;110              insert(rt,0,x);111             end;112           end;113       ‘?‘:begin114           readln(st);115           if (ord(st[1])>ord(‘0‘)) and (ord(st[1])<=ord(‘9‘)) then116            begin117              val(st,rank);118              x:=find(rt,rank);119              if rank+9<=tot then y:=find(rt,rank+11) else y:=find(rt,tot+2);120              splay(x,rt);splay(y,c[x,1]);121              first:=true;print(c[y,0]);writeln;122            end123           else124            begin125              x:=hash(st);126              splay(x,rt);127              writeln(s[c[x,0]]);128            end;129           end;130       end;131     end;132  end;133 134 begin135   assign(input,‘input.txt‘);assign(output,‘output.txt‘);136   reset(input);rewrite(output);137   main;138   close(input);close(output);139 end.                    

  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 using namespace std;  5 const int u=500010,mod=999983;  6 struct splaytree{  7     int l,r,dat,size;  8     #define l(x) t[x].l  9     #define r(x) t[x].r 10     #define dat(x) t[x].dat 11     #define size(x) t[x].size 12 }t[u]; 13 unsigned long long ver[u],temp; 14 int L[u],R[u],head[1000000],sc[u],id[u],next[u]; 15 char name[u][15],str[15]; 16 int n,m,tot,root,i,j,x,y,sco,z,now,rec; 17   18 int hash(int x,int y) 19 { 20     int i,z; 21     for(temp=0,i=1;i<strlen(str);i++) temp=temp*27+str[i]-‘A‘+1; 22     z=temp%mod; 23     for(i=head[z];i;i=next[i]) 24         if(ver[i]==temp) return i; 25     ver[++m]=temp; sc[m]=x; id[m]=y; 26     next[m]=head[z]; head[z]=m; 27     for(i=1;i<strlen(str);i++) name[m][i-1]=str[i]; name[m][i-1]=‘\0‘; 28     return m; 29 } 30   31 inline void update(int x) 32 { 33     size(x)=size(l(x))+size(r(x))+1; 34 } 35   36 inline void zig(int &x) 37 { 38     int y=l(x); l(x)=r(y); r(y)=x; 39     update(x),update(y),x=y; 40 } 41   42 inline void zag(int &x) 43 { 44     int y=r(x); r(x)=l(y); l(y)=x; 45     update(x),update(y),x=y; 46 } 47   48 inline int cmp(int x,int p) 49 { 50     int y=dat(p); 51     if(sc[x]==sc[y]&&id[x]==id[y]) return 0; 52     if(sc[x]>sc[y]||sc[x]==sc[y]&&id[x]<id[y]) return -1; 53     return 1; 54 } 55   56 inline void splay(int &x,int y) 57 { 58     int i; L[0]=R[0]=0; 59     while(1) 60     { 61         i=cmp(y,x); 62         if(!i||!l(x)&&i<0||!r(x)&&i>0) break; 63         if(i<0) 64         { 65             if(cmp(y,l(x))<0) {zig(x); if(!l(x)) break;} 66             R[++R[0]]=x; x=l(x); 67         } 68         else{ 69             if(cmp(y,r(x))>0) {zag(x); if(!r(x)) break;} 70             L[++L[0]]=x; x=r(x); 71         } 72     } 73     L[L[0]+1]=l(x); R[R[0]+1]=r(x); 74     for(i=L[0];i;i--) {r(L[i])=L[i+1]; update(L[i]);} 75     for(i=R[0];i;i--) {l(R[i])=R[i+1]; update(R[i]);} 76     l(x)=L[1]; r(x)=R[1]; update(x); 77 } 78   79 void insert(int x) 80 { 81     tot++; dat(tot)=x; size(tot)=1; 82     if(!root) {root=tot; return;} 83     splay(root,x); 84     if(cmp(x,root)<0) l(tot)=l(root),l(root)=tot; 85     else r(tot)=r(root),r(root)=tot; 86     update(tot),update(root); 87 } 88   89 void clear(int x) 90 { 91     splay(root,x); 92     if(!l(root)) {root=r(root); return;} 93     splay(l(root),x); 94     r(l(root))=r(root); root=l(root); 95     update(root); 96 } 97   98 void ask(int x) 99 {100     splay(root,x);101     printf("%d\n",size(l(root))+1);102 }103  104 void dfs(int x)105 {106     if(l(x)&&now) dfs(l(x));107     if(now) {now--; printf(" %s",name[dat(x)]);}108     if(r(x)&&now) dfs(r(x));109 }110  111 void print(int rank)112 {113     int x;114     for(x=root;;)115         if(size(l(x))+1==rank) break;116         else if(rank<=size(l(x))) x=l(x);117         else rank-=size(l(x))+1,x=r(x);118     printf("%s",name[dat(x)]);119     splay(root,dat(x));120     now=9; if(r(x)) dfs(r(x));121     puts("");122 }123  124 int main()125 {126     cin>>n;127     for(i=1;i<=n;i++)128     {129         scanf("%s",str);130         if(str[0]==‘+‘)131         {132             scanf("%d",&sco);133             rec=m;134             z=hash(sco,i);135             if(rec==m) {clear(z); sc[z]=sco; id[z]=i;}136             insert(z);137         }138         else if(str[1]>=‘0‘&&str[1]<=‘9‘)139         {140             for(j=1,x=0;j<strlen(str);j++) x=x*10+str[j]-‘0‘;141             print(x);142         }143         else ask(hash(0,0));144     }145     return 0;146 }