[loj#3105] [TJOI2019] 甲苯先生的滚榜

题意简述

有 \(n\) 次 \(AC\) ，通过给定函数生成第 \(i\) 次 \(AC\) 的人的序号和罚时。
以 \(AC\) 的题目数为第以关键字排序， \(AC\) 数相同的罚时短的排在前面。
求每有一次 \(AC\) 后，这次 \(AC\) 的人在总排名中排在他前面的有几人（不包括与他罚时、通过题目数都相同的人）。

\(n \leq 10^6\)

想法

显然用平衡树呀！
关键在于选择辣个，鉴于我很懒，所以选了 \(FHQtreap\)

用树状数组维护通过了 \(i\) 道题的总人数，用 \(FHQtreap\) 维护相同 \(AC\) 数的人的罚时。
出现一次新 \(AC\) 后，将它从原有的树中 \(split\) 出去，再加入新的树中。
排名随便算算就好（我太懒了……

总结

\(FHQtreap\) 有两种 \(split\) 方式，分别是根据权值、根据大小，是都可以使用的。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1000005;

void write(int x){
    if(x==0) { putchar('0'); putchar('\n'); return; }
    if(x<0) putchar('-'),x=-x;
    int t=0; char ch[20];
    while(x) ch[t++]=x%10+'0',x/=10;
    for(;t;) putchar(ch[--t]);
    putchar('\n');
}

int n,m;

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

int t[N],num[N];
int c[N];
void add(int x,int y) { while(x<=n) c[x]+=y,x+=x&(-x); }
int sum(int x) {
    int ret=0;
    while(x) ret+=c[x],x-=x&(-x);
    return ret;
}

typedef pair<int,int> Pr;
int val[N],pri[N],ch[N][2],sz[N],cnt;
int rt[N];
void update(int x) { sz[x]=1+sz[ch[x][0]]+sz[ch[x][1]]; }
int merge(int x,int y){
    if(!x || !y) return x+y;
    if(pri[x]>pri[y]) { ch[x][1]=merge(ch[x][1],y); update(x); return x; }
    else{ ch[y][0]=merge(x,ch[y][0]); update(y); return y; }
}
Pr split(int x,int k){//u: val<k v: val>=k
    if(!x) return Pr(0,0);
    if(val[x]<k) {
        Pr y=split(ch[x][1],k);
        ch[x][1]=y.first; update(x);
        return Pr(x,y.second);
    }
    else{
        Pr y=split(ch[x][0],k);
        ch[x][0]=y.second; update(x);
        return Pr(y.first,x);
    }
}
Pr split_sz(int x,int k){//u: sz<=k
    if(!x) return Pr(0,0);
    if(sz[ch[x][0]]>=k){
        Pr y=split_sz(ch[x][0],k);
        ch[x][0]=y.second; update(x);
        return Pr(y.first,x);
    }
    else{
        Pr y=split_sz(ch[x][1],k-sz[ch[x][0]]-1);
        ch[x][1]=y.first; update(x);
        return Pr(x,y.second);
    }
}
int find(int id,int k){
    Pr y=split(rt[id],k);
    Pr x=split_sz(y.second,1);
    rt[id]=merge(y.first,x.second);
    return x.first;
}
int ins(int id,int x){
    Pr y=split(rt[id],val[x]);
    int ret=sz[y.first];
    rt[id]=merge(y.first,merge(x,y.second));
    return ret;
}
int rr;
int rnd() { return rr=1ll*rr*4987657%998244353; }


int main()
{
    int T,u,ti,x;
    scanf("%d",&T);
    lst=7; rr=1;
    while(T--){
        scanf("%d%d",&m,&n);
        scanf("%u",&sd);
        for(int i=1;i<=n;i++){
            u=randNum(sd,lst,m); ti=randNum(sd,lst,m);
            num[u]++; t[u]+=ti;
            if(num[u]-1) add(num[u]-1,-1); add(num[u],1);
            lst=sum(n)-sum(num[u]);
            if(num[u]==1) x=++cnt,val[x]=t[u],pri[x]=rnd(),sz[x]=1;
            else x=find(num[u]-1,t[u]-ti),val[x]+=ti;
            lst+=ins(num[u],x);
            write(lst);
        }
        
        //clear
        for(int i=0;i<=n;i++) c[i]=0,rt[i]=0;
        for(int i=1;i<=m;i++) t[i]=0,num[i]=0;
        for(int i=1;i<=cnt;i++) {
            val[i]=pri[i]=sz[i]=0;
            ch[i][0]=ch[i][1]=0;
        }
        cnt=0;
    }
    
    return 0;
}

[loj#3105] [TJOI2019] 甲苯先生的滚榜

原文：https://www.cnblogs.com/lindalee/p/12488485.html