解题：ZJOI 2006 游戏排名系统

跟i207M学了学重载运算符后找前驱后继，然后就是练练无旋树堆
  1 #include<map>
  2 #include<cstdio>
  3 #include<string>
  4 #include<cstring>
  5 #include<iostream>
  6 #include<algorithm>
  7 using namespace std;
  8 const int N=250005;
  9 struct a
 10 {
 11     int id;
 12     long long sc;
 13     string username;
 14 }dat[N];
 15 bool operator < (a a1,a a2)
 16 {
 17     return (a1.sc==a2.sc)?a1.id<a2.id:a1.sc>a2.sc;
 18 }
 19 int siz[N],son[N][2],rnk[N];
 20 int n,x,y,z,t1,t2,tot,cnt,tim,root;
 21 map<string,a> mp;  string rd; 
 22 void Pushup(int nde)
 23 {
 24     siz[nde]=siz[son[nde][0]]+siz[son[nde][1]]+1;
 25 }
 26 int Create(a tsk)
 27 {
 28     siz[++tot]=1;
 29     dat[tot]=tsk;
 30     rnk[tot]=rand();
 31     return tot;
 32 }
 33 int Merge(int x,int y)
 34 {
 35     if(!x||!y)
 36         return x+y;
 37     else if(rnk[x]<=rnk[y])
 38     {
 39         son[x][1]=Merge(son[x][1],y);
 40         Pushup(x); return x;
 41     }
 42     else 
 43     {
 44         son[y][0]=Merge(x,son[y][0]);
 45         Pushup(y); return y;
 46     }
 47 }
 48 void Split(int nde,int &x,int &y,a tsk)
 49 {
 50     if(!nde) x=y=0;
 51     else
 52     {
 53         if(dat[nde]<tsk)
 54             x=nde,Split(son[nde][1],son[nde][1],y,tsk);
 55         else 
 56             y=nde,Split(son[nde][0],x,son[nde][0],tsk);
 57         Pushup(nde);
 58     }
 59 }
 60 int Query(int nde,int tsk)
 61 {
 62     if(tsk<=siz[son[nde][0]]) return Query(son[nde][0],tsk);
 63     else if(tsk==siz[son[nde][0]]+1) return nde;
 64     else return Query(son[nde][1],tsk-siz[son[nde][0]]-1);
 65 }
 66 void Insert(a tsk)
 67 {
 68     Split(root,x,y,tsk);
 69     root=Merge(Merge(x,Create(tsk)),y);
 70 }
 71 void Delete(a tsk)
 72 {
 73     Split(root,x,y,tsk); tsk.id++;
 74     Split(y,y,z,tsk); root=Merge(x,z);
 75 }
 76 int rnk_query(a tsk)
 77 {
 78     Split(root,x,y,tsk);
 79     int ret=siz[x]+1;
 80     root=Merge(x,y); return ret;
 81 }
 82 string num_query(int tsk)
 83 {
 84     return dat[Query(root,tsk)].username;
 85 }
 86 int main()
 87 {
 88     cin>>n; 
 89     for(int i=1;i<=n;i++)
 90     {
 91         cin>>rd;
 92         if(rd[0]=='+')
 93         {
 94             long long sc; cin>>sc;
 95             rd.erase(rd.begin()),cnt++;    
 96             if(mp.count(rd)) Delete(mp[rd]),cnt--;
 97             Insert(mp[rd]=(a){++tim,sc,rd}); 
 98         }
 99         else 
100         {
101             if(isdigit(rd[1]))
102             {
103                 int q=0;
104                 for(int j=1;j<(int)rd.size();j++) 
105                     q=q*10+rd[j]-'0';
106                 for(int j=q,c=1;j<=cnt&&c<=10;j++,c++)
107                     cout<<num_query(j)<<' '; cout<<endl;
108             }
109             else
110             {
111                 rd.erase(rd.begin());
112                 cout<<rnk_query(mp[rd])<<endl;
113             }
114         }
115     }
116     return 0;
117 }
View Code