P5338 [TJOI2019]甲苯先生的滚榜 FHQ_TREAP

题意：

戳这里

分析：

每个人按照 AC数目 为第一关键字降序，罚时 为第二关键字升序 的排序方式，动态修改，查询排名

这个修改和查询很平衡树，所以我们就上 (fhq) ，将值的大小当做键值，所以我们需要新建一个结构体，然后重载 (<=) 号，剩下操作和普通 (fhq) 一毛一样

代码：

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second

using namespace std;

namespace zzc
{
	typedef unsigned int ui ;
	inline ui read()
	{
		ui x=0,f=1;char ch=getchar();
		while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
		while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
		return x*f;
	}
	
	const int maxn = 1e6+5;
	ui t,n,m,seed,lst=7;
	
	ui randNum( ui& seed , ui last , const ui m)
	{ 
	    seed = seed * 17 + last ; return seed % m + 1; 
	}
	
	namespace fhq_treap
	{
		struct node
		{
			int num,tim;
			node(){}
			node(int num,int tim):num(num),tim(tim){}
			bool operator <=(const node &b)const
			{
				return num==b.num?tim<=b.tim:num>b.num;
			}
		}w[maxn],val[maxn];
		
		int siz[maxn],son[maxn][2],rnd[maxn];
		int cnt,rt;
		
		void clear()
		{
			for(int i=1;i<=cnt;i++) son[i][0]=son[i][1]=siz[i]=0,val[i]=node(0,0);
			cnt=rt=0;	
		}
		
		void pushup(int rt)
		{
			siz[rt]=siz[son[rt][0]]+siz[son[rt][1]]+1;
		}
		
		int new_node(node x)
		{
			int u=++cnt;
			val[u]=x;siz[u]=1;
			rnd[u]=rand();
			return u;
		}
		
		void split(int tmp,node x,int &u,int &v)
		{
			if(!tmp)
			{
				u=0;v=0;
				return ;
			}
			if(val[tmp]<=x)
			{
				u=tmp;
				split(son[u][1],x,son[u][1],v);
				pushup(u);
			}
			else
			{
				v=tmp;
				split(son[v][0],x,u,son[v][0]);
				pushup(v);
			}
		}
		
		int merge(int x,int y)
		{
			if(!x||!y) return x|y;
			if(rnd[x]<rnd[y])
			{
				son[x][1]=merge(son[x][1],y);
				pushup(x);
				return x;
			}
			else
			{
				son[y][0]=merge(x,son[y][0]);
				pushup(y);
				return y;
			}
		}
		
		void del(node k)
		{
			int x,y,z;
			node tmp=k;tmp.tim--;
			split(rt,k,x,z);
			split(x,tmp,x,y);
			y=merge(son[y][0],son[y][1]);
			rt=merge(x,merge(y,z));
		}
		
		void insert(node k)
		{
			int x,y;
			split(rt,k,x,y);
			rt=merge(x,merge(new_node(k),y));
		}
		
		ui query(node k)
		{
			int x,y;k.tim--;
			split(rt,k,x,y);
			ui res=siz[x];
			rt=merge(x,y);
			return res;
		}
		
	}
	using namespace fhq_treap;
	
	void work()
	{
		t=read();
		while(t--)
		{
			ui a,b;
			clear();
			m=read();n=read();seed=read();
			for(ui i=1;i<=n;i++)
			{
				a=randNum(seed,lst,m);
				b=randNum(seed,lst,m);
				del(w[a]);
				w[a].num++;w[a].tim+=b;
				insert(w[a]);
				lst=query(w[a]);
				printf("%u
",lst);
			}
			for(ui j=1;j<=m;j++) w[j]=node(0,0);
		}
	
	}

}

int main()
{
	zzc::work();
	return 0;
}