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

Great_Influence · 2019-05-02 21:27:47 · 题解

第一眼就看出是平衡树裸题。

那么就直接用 pbds 按题意模拟即可。(这个库可是直接就可以用的)

代码:

#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cassert>
#include<iostream>
#include<climits>
#include<vector>
#include<bitset>
#include<queue>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define pb push_back
#define mp make_pair
#define mx(a,b) (a>b?a:b)
#define mn(a,b) (a<b?a:b)
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;
using namespace std;

namespace IO
{
    const uint32 Buffsize=1<<15,Output=1<<24;
    static char Ch[Buffsize],*S=Ch,*T=Ch;
    inline char getc()
    {
        return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
    }
    static char Out[Output],*nowps=Out;

    inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}

    template<typename T>inline void read(T&x)
    {
        x=0;static char ch;T f=1;
        for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
        for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
        x*=f;
    }

    template<typename T>inline void write(T x,char ch='\n')
    {
        if(!x)*nowps++='0';
        if(x<0)*nowps++='-',x=-x;
        static uint32 sta[111],tp;
        for(tp=0;x;x/=10)sta[++tp]=x%10;
        for(;tp;*nowps++=sta[tp--]^48);
        *nowps++=ch;
        if(nowps-Out>=1<<23)flush();
    }

    inline void getstr(char*q)
    {
        register char ch;
        for(ch=getc();!isgraph(ch);ch=getc());
        for(;isgraph(ch);ch=getc())*q++=ch;
        *q='\0';
    }

    inline void getwd(char&x){for(x=getc();!isupper(x);x=getc());}
}
using namespace IO;

void file()
{
#ifndef ONLINE_JUDGE
    FILE*DSD=freopen("water.in","r",stdin);
    FILE*CSC=freopen("water.out","w",stdout);
#endif
}

inline void Chkmin(int&u,int v){u>v?u=v:0;}

inline void Chkmax(int&u,int v){u<v?u=v:0;}

inline void Chkmax(double&u,double v){u<v?u=v:0;}

inline void Chkmax(ll&u,ll v){u<v?u=v:0;}

inline void Chkmin(ll&u,ll v){u>v?u=v:0;}

const int MAXN=1e5+7;

static int n,m;

uint32 seed;

uint32 randnm(uint32&seed,uint32 lst,const uint32 m)
{
    seed=seed*17+lst;return seed%m+1;
}

inline void init(){read(m),read(n),read(seed);}

#include<bits/extc++.h>
using namespace __gnu_pbds;
typedef pair<int,ll>Pr;

tree<Pr,null_type,greater<Pr>,rb_tree_tag,tree_order_statistics_node_update>G;

static int AC[MAXN];

static ll tim[MAXN];

static int last;

const int bl=1e7;

inline void solve()
{
    G.clear();
    Rep(i,1,m)AC[i]=0,tim[i]=1.5e14+i,G.insert(mp(0,tim[i]));
    Rep(i,1,n)
    {
        int ria=randnm(seed,last,m),rib=randnm(seed,last,m);
        G.erase(mp(AC[ria],tim[ria]));
        ++AC[ria],tim[ria]-=(ll)rib*bl;
        G.insert(mp(AC[ria],tim[ria]));
        write(last=G.order_of_key(mp(AC[ria],tim[ria]/bl*bl+bl-1000)));
    }
}

int main()
{
    file();
    static int _;
    read(_),last=7;
    while(_--)init(),solve();
    flush();
    return 0;
}