[BZOJ1056] [HAOI2008] 랭킹 시스템(밸런스 트리 splay)

제목 설명

문제풀이

코드

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;

const int max_n=3e5+5;
const int INF=2e9;

map <string,int> list,score;
map <int,string> name;
int n,tot,totplayer;
string Name,s;
int Score;
int f[max_n],ch[max_n][2],size[max_n],key[max_n],player[max_n];
int root,sz;
int printtot,printcnt;

inline bool get(int x){
    return ch[ f[x] ][1]==x;
}

inline void update(int x){
    if (x){
        size[x]=1;
        if (ch[x][0]) size[x]+=size[ ch[x][0] ];
        if (ch[x][1]) size[x]+=size[ ch[x][1] ];
    }
}

inline void rotate(int x){
    int old=f[x],oldf=f[old],which=get(x);

    ch[old][which]=ch[x][which^1];
    f[ ch[old][which] ]=old;

    ch[x][which^1]=old;
    f[old]=x;

    f[x]=oldf;
    if (oldf)
      ch[oldf][ ch[oldf][1]==old ]=x;

    update(old);
    update(x);
}

inline void splay(int x,int tar){
    for (int fa;(fa=f[x])!=tar;rotate(x))
      if (f[fa]!=tar)
        rotate( (get(x)==get(fa)) ?fa:x);
    if (!tar) root=x;
}

//     x，     y     
inline int find(int x,int y){

    int now=root,ans=0;

    while (1){
        if (x<key[now]) 
          now=ch[now][0];
        else{
            if (x==key[now]){ 
                if (y==player[now]){ 
                    if (ch[now][0])
                      ans+=size[ ch[now][0] ];
                    return ans+1;
                }
                if (y<player[now]) 
                  now=ch[now][0];
                else{ 
                    if (ch[now][0])
                      ans+=size[ ch[now][0] ];
                    ans+=1;
                    now=ch[now][1];
                }
            }
            else{
                if (ch[now][0])
                  ans+=size[ ch[now][0] ];
                ans+=1;
                now=ch[now][1]; 
            }
        }
    }
}

//    x，     
inline int Insert_Find_Pre(int x){
    int now=root,ans;

    while (1){
        if (key[now]<x){
            ans=now;
            if (ch[now][1]) now=ch[now][1];
            else break;
        }
        else
          if (ch[now][0])
            now=ch[now][0];
          else
            break;
    }

    return ans;
}

//       x，     
inline int Insert_Find_Next(int x){
    int now=root,ans;

    while (1){
        if (key[now]>=x){
            ans=now;
            if (ch[now][0]) now=ch[now][0];
            else break;
        }
        else
          if (ch[now][1])
            now=ch[now][1];
          else
            break;
    }

    return ans;
}

//    x，      x     x，     
inline int Delete_Find_Pre(int x,int Name){
    int now=root,ans;

    while (1){
        if (key[now]<x||key[now]==x&&player[now]<Name){
            ans=now;
            if (ch[now][1]) now=ch[now][1];
            else break;
        }
        else
          if (ch[now][0]) 
            now=ch[now][0];
          else
            break;
    }

    return ans;
} 

//    x，      x      x，     
inline int Delete_Find_Next(int x,int Name){
    int now=root,ans;

    while (1){
        if (key[now]>x||key[now]==x&&player[now]>Name){
            ans=now;
            if (ch[now][0]) now=ch[now][0];
            else break;
        }
        else
          if (ch[now][1])
            now=ch[now][1];
          else
            break;
    }

    return ans;
} 

inline void insert(int x,int Name){

    if (root==0){
        root=++sz;
        f[sz]=ch[sz][0]=ch[sz][1]=0;
        size[sz]=1;
        key[sz]=x;
        player[sz]=Name;
        return;
    } 
    if (!ch[root][0]&&!ch[root][1]){
        ch[root][ key[root]<x ]=++sz;
        f[sz]=root;
        ch[sz][0]=ch[sz][1]=0;
        size[sz]=1;
        key[sz]=x;
        player[sz]=Name;
        update(root);
        return;
    }

    int aa=Insert_Find_Pre(x);
    int bb=Insert_Find_Next(x);
    splay(aa,0);
    splay(bb,aa);

    ch[ ch[root][1] ][0]=++sz;
    f[sz]=ch[root][1];
    ch[sz][0]=ch[sz][1]=0;
    size[sz]=1;
    key[sz]=x;
    player[sz]=Name;
    update(ch[root][1]);
    update(root);
}

inline void del(int x,int Name){
    int aa=Delete_Find_Pre(x,Name);
    int bb=Delete_Find_Next(x,Name);
    splay(aa,0);
    splay(bb,aa);

    ch[ ch[root][1] ][0]=0;
    update(ch[root][1]);
    update(root);
}



//     x     
inline int findnum(int x){
    int now=root,ans;
    while (1){
        if (ch[now][0]&&x<=size[ ch[now][0] ])
          now=ch[now][0];
        else{
            int temp=1;
            if (ch[now][0])
              temp+=size[ ch[now][0] ];
            if (x<=temp) return now;
            x-=temp;
            now=ch[now][1];
        }
    }
} 

inline void print(int x){
    int now=x;
    if (ch[now][1]) print(ch[now][1]); 

    printtot++;
    string s=name[player[now]];
    int len=s.length();
    for (int i=0;i<len;++i)
      putchar(s[i]);
    if (printtot!=printcnt) putchar(' ');

    if (ch[now][0]) print(ch[now][0]);
}

inline void Query(int L,int R){
    int y=totplayer-L+1;
    int x=totplayer-(L+R-1)+1;
    //x-1 y+1 
    int aa=findnum(x);
    int bb=findnum(y+2);
    splay(aa,0);
    splay(bb,aa);

    printtot=0; printcnt=R;
    print( ch[ ch[root][1] ][0] );
}




int main(){
// freopen("input.txt","r",stdin);
// freopen("my.out","w",stdout);

    scanf("%d",&n);
    insert(-INF,INF+2);
    insert(INF,INF+1);
    tot=250000+1;

    for (int i=1;i<=n;++i){
        char c=getchar();
        while (c!='+'&&c!='?') c=getchar();

        if (c=='+'){

            Name="";
            char cc;
            while (1){
                cc=getchar();
                if (cc==' ') 
                  break;
                Name=Name+cc; 
            }

            scanf("%d",&Score);

            if (list[Name]){
                del( score[Name],list[Name] );

                list[Name]=--tot;
                name[tot]=Name; 
                score[Name]=Score;

                insert( Score,list[Name] );
            }

            else{
                totplayer++;
                list[Name]=--tot;
                name[tot]=Name;

                score[Name]=Score;
                insert( Score,list[Name] );
            }
        }
        else{
            Name="";
            char cc;
            while (1){
                cc=getchar();
                if (cc=='
') break;
                Name+=cc; 
            }

            if (Name[0]>='0'&&Name[0]<='9'){
                int Index=0;
                int len=Name.length();
                for (int j=0;j<len;++j)
                  Index=Index*10+Name[j]-'0';

                int L=Index;
                int R=min(totplayer-Index+1,10);
                Query(L,R);
                putchar('
');
            }

            else{
                int ans=find( score[Name],list[Name] )-1;
                printf("%d
",totplayer-ans+1);
            }
        }
    }

    return 0; 
}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;

const int max_n=3e5+5;
const int INF=2e9;

map <string,int> list,score;
map <int,string> name;
int n,tot,totplayer;
string Name,s;
int Score;
int f[max_n],ch[max_n][2],size[max_n],key[max_n];
int root,sz;
int printtot,printcnt;

inline void clear(int x){
    ch[x][0]=ch[x][1]=f[x]=size[x]=key[x]=0;
}

inline bool get(int x){
    return ch[ f[x] ][1]==x;
}

inline void update(int x){
    if (x){
        size[x]=1;
        if (ch[x][0]) size[x]+=size[ ch[x][0] ];
        if (ch[x][1]) size[x]+=size[ ch[x][1] ];
    }
}

inline void rotate(int x){
    int old=f[x],oldf=f[old],which=get(x);

    ch[old][which]=ch[x][which^1];
    f[ ch[old][which] ]=old;

    ch[x][which^1]=old;
    f[old]=x;

    f[x]=oldf;
    if (oldf)
      ch[oldf][ ch[oldf][1]==old ]=x;

    update(old);
    update(x);
}

inline void splay(int x,int tar){
    for (int fa;(fa=f[x])!=tar;rotate(x))
      if (f[fa]!=tar)
        rotate( (get(x)==get(fa)) ?fa:x);
    if (!tar) root=x;
}

inline int insert(int x){
    if (root==0){
        sz++;
        ch[sz][0]=ch[sz][1]=f[sz]=0;
        root=sz;
        size[sz]=1;
        key[sz]=x; 
        return sz;
    }

    int now=root,fa=0;

    while(1){
        fa=now;
        now=ch[now][key[now]<x];

        if (now==0){
            sz++;
            ch[sz][0]=ch[sz][1]=0;
            f[sz]=fa;
            size[sz]=1;
            ch[fa][key[fa]<x]=sz;
            key[sz]=x;
            update(fa);
            splay(sz,0);
            break;
        }
    }
    return sz;
}

inline int pre(){
    int now=ch[root][0];
    while (ch[now][1]) now=ch[now][1];
    return now;
}

inline void del(int x,int cnt){
    splay(cnt,0);
    if (!ch[root][0]&&!ch[root][1]){
        clear(root);
        root=0; 
        return;
    }
    if (!ch[root][0]){
        int oldroot=root;
        root=ch[root][1];
        f[root]=0;
        clear(oldroot);
        return; 
    }
    else if (!ch[root][1]){
        int oldroot=root;
        root=ch[root][0];
        f[root]=0;
        clear(oldroot);
        return;
    }

    int leftbig=pre(),oldroot=root;
    splay(leftbig,0);

    ch[root][1]=ch[oldroot][1];
    f[ch[oldroot][1]]=root;

    clear(oldroot);
    update(root); 
}

//     x     
inline int findnum(int x){
    int now=root,ans;
    while (1){
        if (ch[now][0]&&x<=size[ ch[now][0] ])
          now=ch[now][0];
        else{
            int temp=1;
            if (ch[now][0])
              temp+=size[ ch[now][0] ];
            if (x<=temp) return now;
            x-=temp;
            now=ch[now][1];
        }
    }
} 

inline void print(int x){
    int now=x;
    if (ch[now][1]) print(ch[now][1]); 

    printtot++;
    string s=name[now];
    int len=s.length();
    for (int i=0;i<len;++i)
      putchar(s[i]);
    if (printtot!=printcnt) putchar(' ');

    if (ch[now][0]) print(ch[now][0]);
}

inline void Query(int L,int R){
    int y=totplayer-L+1;
    int x=totplayer-(L+R-1)+1;
    //x-1 y+1 
    int aa=findnum(x);
    int bb=findnum(y+2);
    splay(aa,0);
    splay(bb,aa);

    printtot=0; printcnt=R;
    print( ch[ ch[root][1] ][0] );
}

int main(){
// freopen("input.txt","r",stdin);
// freopen("my.out","w",stdout);

    scanf("%d",&n);
    insert(-INF);
    insert(INF);

    for (int i=1;i<=n;++i){
        char c=getchar();
        while (c!='+'&&c!='?') c=getchar();

        //list<string,int>       ，score<string,int>        
        //name[i]<int,string>     i       
        if (c=='+'){

            Name="";
            char cc;
            while (1){
                cc=getchar();
                if (cc==' ') 
                  break;
                Name=Name+cc; 
            }
            scanf("%d",&Score);

            if (list[Name]){
                del( score[Name],list[Name] ); 
                score[Name]=Score;
                int number=insert( Score );
                list[Name]=number;
                name[number]=Name;
            }

            else{
                totplayer++;
                score[Name]=Score;
                int number=insert( Score );
                list[Name]=number;
                name[number]=Name;
            }
        }
        else{
            Name="";
            char cc;
            while (1){
                cc=getchar();
                if (cc=='
') break;
                Name+=cc; 
            }

            if (Name[0]>='0'&&Name[0]<='9'){
                int Index=0;
                int len=Name.length();
                for (int j=0;j<len;++j)
                  Index=Index*10+Name[j]-'0';

                int L=Index;
                int R=min(totplayer-Index+1,10);
                Query(L,R);
                putchar('
');
            }

            else{//       
                splay(list[Name],0);
                int ans=size[ ch[root][0] ]-1;
                printf("%d
",totplayer-ans);
            }
        }
    }

    return 0; 
}