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旋到根然后往右边遍历）
const
maxn=;
type
node=record
son:array[..]of longint;
size,fa,f,t:longint;
str:string;
end;
var
tree:array[..maxn*]of node;
hash,next:array[..maxn*]of longint;
n,tot,time,root,k,num:longint; function hashx(s:string):longint;
var
i:longint;
begin
hashx:=;
for i:= to length(s) do
hashx:=(hashx*+ord(s[i])-ord('A'))mod maxn;
inc(hashx);
end; function get(s:string):longint;
begin
get:=hashx(s);
while (tree[get].str<>s) and (get<>) do
get:=next[get];
end; procedure rotate(x,w:longint);
var
y:longint;
begin
y:=tree[x].fa;
tree[y].son[w]:=tree[x].son[w xor ];
if tree[x].son[w xor ]<> then tree[tree[x].son[w xor ]].fa:=y;
tree[x].son[w xor ]:=y;
if root=y then root:=x
else
if tree[tree[y].fa].son[]=y then tree[tree[y].fa].son[]:=x
else tree[tree[y].fa].son[]:=x;
tree[x].fa:=tree[y].fa;
tree[y].fa:=x;
with tree[y] do
size:=tree[son[]].size++tree[son[]].size;
end; procedure splay(x,z:longint);
var
y:longint;
begin
while tree[x].fa<>z do
begin
y:=tree[x].fa;
if tree[y].fa=z then
if tree[y].son[]=x then rotate(x,)
else rotate(x,)
else
if tree[tree[y].fa].son[]=y then
if tree[y].son[]=x then
begin
rotate(y,);
rotate(x,);
end
else
begin
rotate(x,);
rotate(x,);
end
else
if tree[y].son[]=x then
begin
rotate(x,);
rotate(x,);
end
else
begin
rotate(y,);
rotate(x,);
end;
end;
with tree[x] do
size:=tree[son[]].size++tree[son[]].size;
end; procedure delete(x:longint);
var
l,r:longint;
begin
splay(x,);
l:=tree[x].son[];
r:=tree[x].son[];
if (l=) or (r=) then
begin
root:=l+r;
tree[l+r].fa:=;
tree[x].son[]:=;
tree[x].son[]:=;
end
else
begin
while tree[l].son[]<> do
l:=tree[l].son[];
while tree[r].son[]<> do
r:=tree[r].son[];
splay(l,);
splay(r,l);
tree[r].son[]:=;
dec(tree[r].size);
dec(tree[l].size);
tree[x].fa:=;
end;
end; procedure add(x:longint);
var
now:longint;
begin
if root= then
begin
root:=x;
tree[x].fa:=;
tree[x].size:=;
end
else
begin
now:=root;
while true do
begin
inc(tree[now].size);
if (tree[x].f>tree[now].f) or ((tree[x].f=tree[now].f) and (tree[x].t<tree[now].t)) then
if tree[now].son[]= then break
else now:=tree[now].son[]
else
if tree[now].son[]= then break
else now:=tree[now].son[];
end;
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[]:=x
else tree[now].son[]:=x;
tree[x].size:=;
tree[x].fa:=now;
end;
splay(x,);
end; procedure insert(s:string;x:longint);
var
z:longint;
begin
z:=get(s);
if z> then
begin
delete(z);
tree[z].t:=time;
tree[z].f:=x;
add(z);
end
else
begin
z:=hashx(s);
inc(num);
if tree[z].str='' then
begin
tree[z].str:=s;
tree[z].t:=time;
tree[z].f:=x;
add(z);
end
else
begin
while next[z]<> do
z:=next[z];
inc(tot);
next[z]:=tot;
tree[tot].str:=s;
tree[tot].t:=time;
tree[tot].f:=x;
add(tot);
end;
end;
end; function find(x:longint):longint;
var
now:longint;
begin
now:=root;
while true do
begin
if x<=tree[tree[now].son[]].size then now:=tree[now].son[]
else
if x=tree[tree[now].son[]].size+ then exit(now)
else
begin
dec(x,tree[tree[now].son[]].size+);
now:=tree[now].son[];
end;
end;
end; procedure dfs(now:longint);
begin
if k= then exit;
if tree[now].son[]<> then dfs(tree[now].son[]);
if k= then exit;
inc(k);
write(' ',tree[now].str);
if k= then exit;
if tree[now].son[]<> then dfs(tree[now].son[]);
end; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; procedure main;
var
x:longint;
c:char;
s:string;
begin
readln(n);
tot:=maxn;
for time:= to n do
begin
read(c);
if c='+' then
begin
read(c);
s:='';
while c<>' ' do
begin
s:=s+c;
read(c);
end;
readln(x);
insert(s,x);
end
else
if c='?' then
begin
readln(s);
if (ord(s[])>=ord('A')) and (ord(s[])<=ord('Z')) then
begin
splay(get(s),);
writeln(tree[tree[root].son[]].size+);
end
else
begin
val(s,x);
splay(find(x),);
write(tree[root].str);
if num>x then splay(find(min(num,x+)),root);
k:=;
if tree[root].son[]<> then dfs(tree[root].son[]);
writeln;
end;
end;
end;
end; begin
main;
end.