题解 P5338 【[TJOI2019]甲苯先生的滚榜】

· · 题解

其实这个题 fhqtreap 也是可做的，这题的时间瓶颈实际上在输出而不在平衡树。

这题只有两个操作：

第一个操作应该人人都会，第二个操作先删了再加进去就好了。

至于题数和罚时，就重新写个类就行了。

#include<bits/stdc++.h>
using namespace std;
int n,m,root;
inline int read()
{
    int re=0,k=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')k=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){re=re*10+ch-48;ch=getchar();}
    return re*k;
}
int tot,ans,s[100005],ls;
struct st{//写个新的val类
    int ria,rib;
    bool operator <(const st b)const{
        if(ria==b.ria)return rib<b.rib;
        else return ria>b.ria;
    }
    bool operator <=(const st b)const{
        if(ria==b.ria)return rib<=b.rib;
        else return ria>=b.ria;
    }
}a[100005];
struct ss{
    int lson,rson,rnd,sz,cnt;st val;
}e[200005];
----------平衡树分割线----------
void push_up(int x)
{
    e[x].sz=e[e[x].lson].sz+e[e[x].rson].sz+e[x].cnt;
}
int merge(int x,int y)
{
    if(!x||!y)return x|y;
    if(e[x].rnd<e[y].rnd)
    {
        e[x].rson=merge(e[x].rson,y);
        push_up(x);return x;
    }
    else
    {
        e[y].lson=merge(x,e[y].lson);
        push_up(y);return y;
    }
}
void split(st k,int now,int &x,int &y)
{
    if(!now)
    {
        x=y=0;
    }
    else
    {
        if(e[now].val<=k)
        {
            x=now;
            split(k,e[now].rson,e[now].rson,y);
        }
        else
        {
            y=now;
            split(k,e[now].lson,x,e[now].lson);
        }
    }
    push_up(now);
}
int new_node(st k)
{
    int now;
    if(ls)now=s[ls--];//写上垃圾回收节省空间
    else now=++tot;
    e[now].sz=e[now].cnt=1;
    e[now].val=k;
    e[now].rnd=rand();
    e[now].lson=e[now].rson=0;
    return now;
}
void insert(st x)
{
    int l,r;
    split(x,root,l,r);
    l=merge(l,new_node(x));
    root=merge(l,r);
}
void del(st x)
{
    int l,a,r;st y=x;
    y.rib--;
    split(x,root,l,r);
    split(y,l,l,a);
    s[++ls]=a;
    a=merge(e[a].lson,e[a].rson);
    root=merge(merge(l,a),r);
}
int ask_val(st x)
{
    int l,r;
    x.rib--;
    split(x,root,l,r);
    int re=e[l].sz+1;
    root=merge(l,r);
    return re-1;
}
-----------分割线结束-----------
typedef unsigned int ui;
    ui randNum(ui& seed, ui last, const ui m) {
    seed = seed * 17 + last;
    return seed % m + 1;
}
ui seed,last=7;
inline void write(int x)//这个必须要，不然会t得很惨
{
    if(x<10)
    {
        putchar(x+48);
        return;
    }
    write(x/10),write(x%10);
}
int main()
{
    int t=read();
    while(t--)
    {
    srand(19260817);
    m=read();n=read();seed=read();
    root=ls=tot=0;
    for(int i=1;i<=m;i++)
        a[i].ria=a[i].rib=0,insert(a[i]);
    int u,v;
    for(int i=1;i<=n;i++)
    {
        u=randNum(seed,last,m);
        v=randNum(seed,last,m);
        del(a[u]);
        a[u].ria++;a[u].rib+=v;
        insert(a[u]);
        last=ask_val(a[u]);
        write(last);
        putchar('\n');  
    }
    }
}