[HAOI2008]排名系统[Zjoi2006]GameZ游戏排名系统

Description

排名系统通常要应付三种请求&＃xff1a;上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名

记录。当某个玩家上传自己最新的得分记录时&＃xff0c;他原有的得分记录会被删除。为了减轻服务器负担&＃xff0c;在返回某个区

段内的排名记录时&＃xff0c;最多返回10条记录。

Input

第一行是一个整数n&＃xff08;n>&＃61;10&＃xff09;表示请求总数目。接下来n行,每行包含了一个请求。请求的具体格式如下&＃xff1a; &＃43;Na

me Score 上传最新得分记录。Name表示玩家名字&＃xff0c;由大写英文字母组成&＃xff0c;不超过10个字符。Score为最多8位的正

整数。 ?Name 查询玩家排名。该玩家的得分记录必定已经在前面上传。 ?Index 返回自第Index名开始的最多10名

玩家名字。Index必定合法&＃xff0c;即不小于1&＃xff0c;也不大于当前有记录的玩家总数。

Sample Input

Input

20
&＃43;ADAM 1000000
&＃43;BOB 1000000
&＃43;TOM 2000000
&＃43;CATHY 10000000
?TOM
?1
&＃43;DAM 100000
&＃43;BOB 1200000
&＃43;ADAM 900000
&＃43;FRANK 12340000
&＃43;LEO 9000000
&＃43;KAINE 9000000
&＃43;GRACE 8000000
&＃43;WALT 9000000
&＃43;SANDY 8000000
&＃43;MICK 9000000
&＃43;JACK 7320000
?2
?5
?KAINE

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

说明

&＃43;ADAM 1000000 加入ADAM的得分记录

&＃43;BOB 1000000 加入BOB的得分记录

&＃43;TOM 2000000 加入TOM的得分记录

&＃43;CATHY 10000000 加入CATHY的得分记录

?TOM 输出TOM目前排名

?1 目前有记录的玩家总数为4&＃xff0c;因此应输出第1名到第4名。

&＃43;DAM 100000 加入DAM的得分记录

&＃43;BOB 1200000 更新BOB的得分记录

&＃43;ADAM 900000 更新ADAM的得分记录&＃xff08;即使比原来的差&＃xff09;

&＃43;FRANK 12340000 加入FRANK的得分记录

&＃43;LEO 9000000 加入LEO的得分记录

&＃43;KAINE 9000000 加入KAINE的得分记录

&＃43;GRACE 8000000 加入GRACE的得分记录

&＃43;WALT 9000000 加入WALT的得分记录

&＃43;SANDY 8000000 加入SANDY的得分记录

&＃43;MICK 9000000 加入MICK的得分记录

&＃43;JACK 7320000 加入JACK的得分记录

?2 目前有记录的玩家总数为12&＃xff0c;因此应输出第2名到第11名。

?5 输出第5名到第13名。

?KAINE 输出KAINE的排名

[数据范围]

20%数据满足N<&＃61;100

100%数据满足N<&＃61;250000

写了5个小时的splay&＃xff0c;硬是没跳出来&＃xff08;WA代码还在COGS上呆着&＃xff09;

后来弃疗&＃xff0c;直接pd_ds&＃xff0c;1A。

#include
#include
#include
#include
#include
using namespace std;
using namespace __gnu_pbds;
class P{
public:string name;int val,tim;P(string n&＃61;"",int v&＃61;0,int t&＃61;0):name(n),val(v),tim(t){}
}z;
class Compare{
public:bool operator ()(const P &a,const P &b)const{if(a.val>b.val) return 1;if(a.valreturn 0;if(a.timreturn 1;if(a.tim>b.tim) return 0;return a.name<b.name;}
};
typedef cc_hash_table<string,P> hs;
typedef tree bbt;
hs ys;
hs::point_iterator ith;
bbt T;
bbt::iterator itt;
inline int read(){int x&＃61;0,f&＃61;1;char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;){x&＃61;x*10&＃43;ch-&＃39;0&＃39;;ch&＃61;getchar();}return x*f;
}
int main(){int n;char s[20];n&＃61;read();for(int i&＃61;1,x;i<&＃61;n;i&＃43;&＃43;){scanf("%s",s);if(s[0]&＃61;&＃61;&＃39;&＃43;&＃39;){//upload recodx&＃61;read();ith&＃61;ys.find(s&＃43;1);if(ith!&＃61;ys.end()) T.erase(ith->second);z&＃61;P(s&＃43;1,x,i);ys[s&＃43;1]&＃61;z;T.insert(z);}else if(s[1]>&＃61;&＃39;0&＃39;&&s[1]<&＃61;&＃39;9&＃39;){//query by orderx&＃61;atoi(s&＃43;1);itt&＃61;T.find_by_order(x-1);int lim&＃61;min(10,(int)ys.size()-x&＃43;1);for(int j&＃61;1;j<&＃61;lim;j&＃43;&＃43;){printf("%s",itt->name.c_str());if(j!&＃61;lim) putchar(&＃39; &＃39;);itt&＃43;&＃43;;}if(i!&＃61;n) putchar(&＃39;\n&＃39;);}else{//query by nameprintf("%d",T.order_of_key(ys[s&＃43;1])&＃43;1);if(i!&＃61;n) putchar(&＃39;\n&＃39;);}}return 0;
}