[原创][HAOI2008] 排名系统 & [ZJOI2006] GameZ游戏排名系统 [SPLAY]【数据结构】

# include <bits/stdc++.h>
typedef long long int LL ;
using namespace std;

const int N   = 300000+7;
const LL INF = 1000000000000000000LL;
/******************************************************/

int n;string ss,s;

map<string,LL>mmp;
map<LL,string>mmp2;
int ch[N][2];  //ch[][0] lson ch[][1] rson
int f[N];      //father
int sz[N];     //size
LL val[N];    //value of node_i
int cnt[N];    // counts of the node_i
int root;      //root of splay-tree
int tot;       //tot,total,is the number of node of tree

void pushup(int x){
    if(x)sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
}

void rotate(int x,int k){   // k = 0 左旋， k = 1 右旋
    int y=f[x];int z=f[y];
    ch[y][!k]=ch[x][k];if(ch[x][k])f[ch[x][k]]=y;
    f[x]=z;if(z)ch[z][ch[z][1]==y]=x;
    f[y]=x;ch[x][k]=y;
    pushup(y),pushup(x);
}

void splay(int x,int goal){
    for(int y=f[x];f[x]!=goal;y=f[x])
        rotate(x,(ch[y][0]==x));
    if(goal==0) root=x;
}

void newnode(int rt,LL v,int fa){
    f[rt]=fa;val[rt]=v,sz[rt]=cnt[rt]=1;
    ch[rt][0]=ch[rt][1]=0;
}

void delnode(int &rt){ //其实是为内存回收做准备的  回头再完善
    f[rt]=val[rt]=sz[rt]=cnt[rt]=0;
    ch[rt][0]=ch[rt][1]=rt=0;
}

/***************************以下是DEBUG***************************/

void Traversal(int rt){
    if(!rt) return;
    Traversal(ch[rt][0]);
    printf("%d f[]=%d sz[]=%d lson=%d rson=%d val[]=%lld\n",rt,f[rt],sz[rt],ch[rt][0],ch[rt][1],val[rt]);
    Traversal(ch[rt][1]);
}
void debug(){
    printf("ROOT = %d <---\n",root);
    Traversal(root);
}

/**************************以下是前置操作**************************/

//以x为根的子树 的极值点  0 极小 1 极大
int extreme(int x,int k){
    while(ch[x][k])x=ch[x][k];splay(x,0);
    return x;
}
//以x为根的子树 第k个数的位置
int kth(int x,int k){
    if(sz[ch[x][0]]+1<=k&&k<=sz[ch[x][0]]+cnt[x]) return x;
    else if(ch[x][0]&&sz[ch[x][0]]>=k) return kth(ch[x][0],k);
    else return kth(ch[x][1],k-sz[ch[x][0]]-cnt[x]);
}
int search(int rt,LL x){
        if(ch[rt][0]&&val[rt]>x) return search(ch[rt][0],x);
    else if(ch[rt][1]&&val[rt]<x)return search(ch[rt][1],x);
    else return rt;
}
/***************************以下是正经操作*************************/
//前驱
int prec(LL x){
    int k=search(root,x);
    splay(k,0);//debug();
    if(val[k]<x) return k;
    return extreme(ch[k][0],1);
}
//后继
int sufc(LL x){
    int k=search(root,x);
    splay(k,0);//debug();
    if(val[k]>x) return k;
    return extreme(ch[k][1],0);
}
int rk(LL x){
    int k=search(root,x);
    splay(k,0);
    return sz[ch[root][0]]+1;
}
//按照二叉排序树性质插入x
void _insert(LL x){
    int p=prec(x),s=sufc(x);
    splay(p,0);splay(s,p);
    newnode(++tot,x,ch[root][1]);
    ch[ch[root][1]][0]=tot;
    for(int z=ch[root][1];z;z=f[z])pushup(z);

    splay(tot,0);
}

void _delete(LL x){
    int p=prec(x),s=sufc(x);
    splay(p,0);splay(s,p);
    ch[ch[root][1]][0]=0;
    delnode(ch[ch[root][1]][0]);
    for(int yy=s;yy;yy=f[yy]) pushup(yy);
}


LL mystack[100],len;
void dfs(int rt){
    if(!rt) return ;
    dfs(ch[rt][0]);
    mystack[++len]=val[rt];
    dfs(ch[rt][1]);
}

void solve(int x){

    int y=kth(root,x-1);
    int z=kth(root,min(x+10,sz[root]));
    splay(y,0),splay(z,y);
    len=0;
    dfs(ch[ch[root][1]][0]);
    for(int i=1;i<len;i++)
        cout<<mmp2[mystack[i]]<<" ";
    cout<<mmp2[mystack[len]]<<endl;
}

int main(){
    mmp.clear();mmp2.clear();
    cin>>n;
    tot=0,root=1;
    newnode(++tot,-INF,0),newnode(++tot,INF,root);
    ch[root][1]=tot;

    for(int i=1,sc;i<=n;i++){//debug();
        cin>>s;
        ss="";
        for(int i=1;i<s.size();i++) ss+=s[i];
        if(s[0]=='+'){
            cin>>sc;
            if(mmp[ss]!=0) _delete(mmp[ss]);
            mmp[ss]=(LL)sc*-1000000+i;
            mmp2[mmp[ss]]=ss;
            _insert(mmp[ss]);
        }
        else {
            if('0'<=ss[0]&&ss[0]<='9'){
                sc=0;
                for(int j=0;j<ss.size();j++) sc=(sc<<3)+(sc<<1)+ss[j]-'0';
                solve(sc+1);
            }
            else{
                cout<<rk(mmp[ss])-1<<endl;
            }
        }

    }
    return 0;
}