1056: [HAOI2008]排名系统

Description

排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回10条记录。
Input

第一行是一个整数n（n>=10）表示请求总数目。接下来n行,每行包含了一个请求。请求的具体格式如下： +Name Score 上传最新得分记录。Name表示玩家名字，由大写英文字母组成，不超过10个字符。Score为最多8位的正整数。 ?Name 查询玩家排名。该玩家的得分记录必定已经在前面上传。 ?Index 返回自第Index名开始的最多10名玩家名字。Index必定合法，即不小于1，也不大于当前有记录的玩家总数。
Output

对于?Name格式的请求，应输出一个整数表示该玩家当前的排名。对于?Index格式的请求，应在一行中依次输出从第Index名开始的最多10名玩家姓名，用一个空格分隔。
Sample Input
20
+ADAM 1000000 加入ADAM的得分记录
+BOB 1000000 加入BOB的得分记录
+TOM 2000000 加入TOM的得分记录
+CATHY 10000000 加入CATHY的得分记录
?TOM 输出TOM目前排名
?1 目前有记录的玩家总数为4，因此应输出第1名到第4名。
+DAM 100000 加入DAM的得分记录
+BOB 1200000 更新BOB的得分记录
+ADAM 900000 更新ADAM的得分记录（即使比原来的差）
+FRANK 12340000 加入FRANK的得分记录
+LEO 9000000 加入LEO的得分记录
+KAINE 9000000 加入KAINE的得分记录
+GRACE 8000000 加入GRACE的得分记录
+WALT 9000000 加入WALT的得分记录
+SANDY 8000000 加入SANDY的得分记录
+MICK 9000000 加入MICK的得分记录
+JACK 7320000 加入JACK的得分记录
?2 目前有记录的玩家总数为12，因此应输出第2名到第11名。
?5 输出第5名到第13名。
?KAINE 输出KAINE的排名
Sample Output
2
CATHY TOM ADAM BOB
CATHY LEO KAINE WALT MICK GRACE SANDY JACK TOM BOB
WALT MICK GRACE SANDY JACK TOM BOB ADAM DAM
4

HINT

20%数据满足N<=100 100%数据满足N<=250000

唉，splay真的不是很熟练啊

又调了一上午，不过还是有一点收获的，每次发现超时都是因为找答案的方法不够好（当你要l到r的答案时，1.把l到r全部旋到一起 2.把l旋到根然后往右边遍历）

  1 const
  2     maxn=200007;
  3 type
  4     node=record
  5       son:array[0..1]of longint;
  6       size,fa,f,t:longint;
  7       str:string;
  8     end;
  9 var
 10     tree:array[0..maxn*2]of node;
 11     hash,next:array[0..maxn*2]of longint;
 12     n,tot,time,root,k,num:longint;
 13  
 14 function hashx(s:string):longint;
 15 var
 16     i:longint;
 17 begin
 18     hashx:=0;
 19     for i:=1 to length(s) do
 20       hashx:=(hashx*27+ord(s[i])-ord('A'))mod maxn;
 21     inc(hashx);
 22 end;
 23  
 24 function get(s:string):longint;
 25 begin
 26     get:=hashx(s);
 27     while (tree[get].str<>s) and (get<>0) do
 28       get:=next[get];
 29 end;
 30  
 31 procedure rotate(x,w:longint);
 32 var
 33     y:longint;
 34 begin
 35     y:=tree[x].fa;
 36     tree[y].son[w]:=tree[x].son[w xor 1];
 37     if tree[x].son[w xor 1]<>0 then tree[tree[x].son[w xor 1]].fa:=y;
 38     tree[x].son[w xor 1]:=y;
 39     if root=y then root:=x
 40     else
 41       if tree[tree[y].fa].son[0]=y then tree[tree[y].fa].son[0]:=x
 42       else tree[tree[y].fa].son[1]:=x;
 43     tree[x].fa:=tree[y].fa;
 44     tree[y].fa:=x;
 45     with tree[y] do
 46       size:=tree[son[0]].size+1+tree[son[1]].size;
 47 end;
 48  
 49 procedure splay(x,z:longint);
 50 var
 51     y:longint;
 52 begin
 53     while tree[x].fa<>z do
 54       begin
 55         y:=tree[x].fa;
 56         if tree[y].fa=z then
 57           if tree[y].son[0]=x then rotate(x,0)
 58           else rotate(x,1)
 59         else
 60           if tree[tree[y].fa].son[0]=y then
 61             if tree[y].son[0]=x then
 62               begin
 63                 rotate(y,0);
 64                 rotate(x,0);
 65               end
 66             else
 67               begin
 68                 rotate(x,1);
 69                 rotate(x,0);
 70               end
 71           else
 72             if tree[y].son[0]=x then
 73               begin
 74                 rotate(x,0);
 75                 rotate(x,1);
 76               end
 77             else
 78               begin
 79                 rotate(y,1);
 80                 rotate(x,1);
 81               end;
 82       end;
 83     with tree[x] do
 84       size:=tree[son[0]].size+1+tree[son[1]].size;
 85 end;
 86  
 87 procedure delete(x:longint);
 88 var
 89     l,r:longint;
 90 begin
 91     splay(x,0);
 92     l:=tree[x].son[0];
 93     r:=tree[x].son[1];
 94     if (l=0) or (r=0) then
 95       begin
 96         root:=l+r;
 97         tree[l+r].fa:=0;
 98         tree[x].son[0]:=0;
 99         tree[x].son[1]:=0;
100       end
101     else
102       begin
103         while tree[l].son[1]<>0 do
104           l:=tree[l].son[1];
105         while tree[r].son[0]<>0 do
106           r:=tree[r].son[0];
107         splay(l,0);
108         splay(r,l);
109         tree[r].son[0]:=0;
110         dec(tree[r].size);
111         dec(tree[l].size);
112         tree[x].fa:=0;
113       end;
114 end;
115  
116 procedure add(x:longint);
117 var
118     now:longint;
119 begin
120     if root=0 then
121       begin
122         root:=x;
123         tree[x].fa:=0;
124         tree[x].size:=1;
125       end
126     else
127       begin
128         now:=root;
129         while true do
130           begin
131             inc(tree[now].size);
132             if (tree[x].f>tree[now].f) or ((tree[x].f=tree[now].f) and (tree[x].t<tree[now].t)) then
133               if tree[now].son[0]=0 then break
134               else now:=tree[now].son[0]
135             else
136               if tree[now].son[1]=0 then break
137               else now:=tree[now].son[1];
138           end;
139         if (tree[x].f>tree[now].f) or ((tree[x].f=tree[now].f) and (tree[x].t<tree[now].t)) then tree[now].son[0]:=x
140         else tree[now].son[1]:=x;
141         tree[x].size:=1;
142         tree[x].fa:=now;
143       end;
144 splay(x,0);
145 end;
146  
147 procedure insert(s:string;x:longint);
148 var
149     z:longint;
150 begin
151     z:=get(s);
152     if z>0 then
153       begin
154         delete(z);
155         tree[z].t:=time;
156         tree[z].f:=x;
157         add(z);
158       end
159     else
160       begin
161         z:=hashx(s);
162         inc(num);
163         if tree[z].str='' then
164           begin
165             tree[z].str:=s;
166             tree[z].t:=time;
167             tree[z].f:=x;
168             add(z);
169           end
170         else
171           begin
172             while next[z]<>0 do
173               z:=next[z];
174             inc(tot);
175             next[z]:=tot;
176             tree[tot].str:=s;
177             tree[tot].t:=time;
178             tree[tot].f:=x;
179             add(tot);
180           end;
181       end;
182 end;
183  
184 function find(x:longint):longint;
185 var
186     now:longint;
187 begin
188     now:=root;
189     while true do
190       begin
191         if x<=tree[tree[now].son[0]].size then now:=tree[now].son[0]
192         else
193           if x=tree[tree[now].son[0]].size+1 then exit(now)
194           else
195             begin
196               dec(x,tree[tree[now].son[0]].size+1);
197               now:=tree[now].son[1];
198             end;
199       end;
200 end;
201  
202 procedure dfs(now:longint);
203 begin
204     if k=10 then exit;
205     if tree[now].son[0]<>0 then dfs(tree[now].son[0]);
206     if k=10 then exit;
207     inc(k);
208     write(' ',tree[now].str);
209     if k=10 then exit;
210     if tree[now].son[1]<>0 then dfs(tree[now].son[1]);
211 end;
212  
213 function min(x,y:longint):longint;
214 begin
215     if x<y then exit(x);
216     exit(y);
217 end;
218  
219 procedure main;
220 var
221     x:longint;
222     c:char;
223     s:string;
224 begin
225     readln(n);
226     tot:=maxn;
227     for time:=1 to n do
228       begin
229         read(c);
230         if c='+' then
231           begin
232             read(c);
233             s:='';
234             while c<>' ' do
235               begin
236                 s:=s+c;
237                 read(c);
238               end;
239             readln(x);
240             insert(s,x);
241           end
242         else
243           if c='?' then
244           begin
245             readln(s);
246             if (ord(s[1])>=ord('A')) and (ord(s[1])<=ord('Z')) then
247               begin
248                 splay(get(s),0);
249                 writeln(tree[tree[root].son[0]].size+1);
250               end
251             else
252               begin
253                 val(s,x);
254                 splay(find(x),0);
255                 write(tree[root].str);
256                 if num>x then splay(find(min(num,x+9)),root);
257                 k:=1;
258                 if tree[root].son[1]<>0 then dfs(tree[root].son[1]);
259                 writeln;
260               end;
261           end;
262       end;
263 end;
264  
265 begin
266     main;
267 end.

View Code