LG5338/BZOJ5509/LOJ3105 「TJOI2019」甲苯先生的滚榜 Treap

问题描述

LG5338

LOJ3105

BZOJ5509

---

题解

建立一棵\(\mathrm{Treap}\)，把原来的\(val\)换成两个值\(ac,tim\)

原来的比较\(val_a<val_b\)改成（设两个结点分别为\(node_a,node_b\)）：

1.若\(ac_a>ac_b\)，则\(node_a<node_b\)

2.若\(1\)不成立，若\(ac_a=ac_b,tim_a<tim_b\)，则\(node_a<node_b\)

3.若\(1,2\)均不成立，则\(node_a>node_b\)

---

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template<typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') fh=-1,ch=getchar();
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

const int INF=0x3f3f3f3f;
const int maxm=1000000+7;

int n,T,root;

unsigned seed,las=7,m;

typedef unsigned int ui;
    ui randNum(ui& seed, ui last, ui m) {
    seed = seed * 17 + last;
    return seed % m + 1;
}

int dat[maxm],size[maxm],cnt[maxm],ac[maxm],tim[maxm];
int ch[maxm][2],tot;

int nowac[maxm*10],nowtim[maxm*10];

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

int New(int a,int b){
    dat[++tot]=rand(),size[tot]=cnt[tot]=1,ac[tot]=a,tim[tot]=b;
    return tot;
}

void build(){
    tot=0;
    root=New(INF,-INF);ch[root][1]=New(-INF,INF);
    pushup(root);
}

void rotate(int &id,int dir){
    int tmp=ch[id][dir xor 1];
    ch[id][dir xor 1]=ch[tmp][dir];
    ch[tmp][dir]=id;id=tmp;
    pushup(ch[id][dir]);pushup(id);
}

void insert(int &id,int a,int b){
    if(!id){
        id=New(a,b);return;
    }
    if(a==ac[id]&&b==tim[id]) cnt[id]++;
    else{
        int d;
        if(a>ac[id]) d=0;
        else if(a==ac[id]){
            if(b<tim[id]) d=0;
            else d=1;
        }
        else d=1;
        insert(ch[id][d],a,b);
        if(dat[id]<dat[ch[id][d]]) rotate(id,d xor 1);
    }
    pushup(id);
}

void remove(int &id,int a,int b){
    if(!id) return;
    if(ac[id]==a&&tim[id]==b){
        if(cnt[id]>1){
            cnt[id]--;pushup(id);return;
        }
        if(ch[id][0]||ch[id][1]){
            if(!ch[id][1]||dat[ch[id][0]]>dat[ch[id][1]]){
                rotate(id,1);remove(ch[id][1],a,b);
            }
            else{
                rotate(id,0);remove(ch[id][0],a,b);
            }
            pushup(id);
        }
        else id=0;
        return;
    }
    if(a>ac[id]){
        remove(ch[id][0],a,b);
    }
    else if(a==ac[id]){
        if(b<tim[id]) remove(ch[id][0],a,b);
        else remove(ch[id][1],a,b);
    }
    else remove(ch[id][1],a,b);
    pushup(id);
}

int get_rank(int id,int a,int b){
    if(!id) return 0;
    if(a==ac[id]&&b==tim[id]) return size[ch[id][0]]+1;
    if(a>ac[id]) return get_rank(ch[id][0],a,b);
    else if(a==ac[id]&&b<tim[id]) return get_rank(ch[id][0],a,b);
    return size[ch[id][0]]+cnt[id]+get_rank(ch[id][1],a,b);
}

int TTTT;

int main(){
    srand(28910);read(TTTT);
    while(TTTT--){
        build();memset(ch,0,sizeof(ch));
        memset(nowac,0,sizeof(nowac));memset(nowtim,0,sizeof(nowtim));
        read(m);read(n);read(seed);
        for(int i=1;i<=n;i++){
            int x,y;
            x=randNum(seed,las,m),y=randNum(seed,las,m);
            remove(root,nowac[x],nowtim[x]);
            nowac[x]++,nowtim[x]+=y;
//            insert(root,nowac[x],nowtim[y]);
            insert(root,nowac[x],nowtim[x]);//错误笔记：弄错x,y
//            las=get_rank(root,nowac[x],nowtim[y])-2;
            las=get_rank(root,nowac[x],nowtim[x])-2;//错误笔记：弄错x,y
            printf("%d\n",las);
        }
    }
    return 0;
}