自动搬运

查看原文

来自洛谷，原作者为

	clamee AFO

搬运于2025-08-24 22:09:44，当前版本为作者最后更新于2020-02-10 21:19:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

这题只有两个操作：

• 求某个值的排名-1

• 修改某个值

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

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

#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');	
	}
	}
}