pb_ds 裸题，写写权值分块试试能不能过……觉得够呛。
P.S.cin读入大量数据会RE。
1 #include<cstdio> 2 #include<cctype> 3 #include<string> 4 #include<ext/pb_ds/assoc_container.hpp> 5 #include<ext/pb_ds/tree_policy.hpp> 6 using namespace std; 7 using namespace __gnu_cxx; 8 using namespace __gnu_pbds; 9 int Res,Num;char C,CH[20]; 10 inline int G() 11 { 12 Res=0;C='*'; 13 while(C<'0'||C>'9')C=getchar(); 14 while(C>='0'&&C<='9'){Res=Res*10+(C-'0');C=getchar();} 15 return Res; 16 } 17 inline void P(int x) 18 { 19 Num=0;if(!x){putchar('0');puts("");return;} 20 while(x>0)CH[++Num]=x%10,x/=10; 21 while(Num)putchar(CH[Num--]+48); 22 puts(""); 23 } 24 int n,v,en; 25 char tmps[20]; 26 string s; 27 struct Point 28 {string x;int y,z; 29 Point(const string &a,const int &b,const int &c){x=a;y=b;z=c;} 30 Point(){}}; 31 bool operator < (const Point &a,const Point &b){return a.y!=b.y ? a.y<b.y : a.z>b.z;} 32 tree<Point,null_mapped_type,less<Point>,rb_tree_tag,tree_order_statistics_node_update> T; 33 typedef tree<Point,null_mapped_type,less<Point>,rb_tree_tag,tree_order_statistics_node_update>::iterator ITER; 34 map<string,int>ma,ma2; 35 inline bool is_name(const string &x) 36 { 37 int len=x.length(); 38 for(int i=0;i<len;i++) if(!isalpha(x[i])) return false; 39 return true; 40 } 41 inline int to_num(const string &x) 42 { 43 int res=0,base=1,len=x.length(); 44 for(int i=len-1;i>=0;i--) 45 { 46 res+=(x[i]-'0')*base; 47 base*=10; 48 } 49 return res; 50 } 51 int main() 52 { 53 n=G(); 54 for(int i=1;i<=n;i++) 55 { 56 scanf("%s",tmps); s=tmps; 57 if(s[0]=='+') 58 { 59 s.erase(0,1); 60 v=G(); 61 if(ma.find(s)!=ma.end()) T.erase(T.find(Point(s,ma[s],ma2[s]))); 62 ma[s]=v; 63 T.insert(Point(s,v,++en)); 64 ma2[s]=en; 65 } 66 else 67 { 68 s.erase(0,1); 69 if(is_name(s)) P(T.size()-T.order_of_key(Point(s,ma[s],ma2[s]))); 70 else 71 { 72 v=to_num(s); 73 int i=1; ITER it=T.find_by_order(T.size()-v); 74 for(;;it--,i++) 75 { 76 printf("%s",(*it).x.c_str()); 77 if(it==T.begin()||i==10) 78 { 79 puts(""); 80 break; 81 } 82 putchar(' '); 83 } 84 } 85 } 86 } 87 return 0; 88 }