自动搬运

查看原文

来自洛谷，原作者为

	MeowScore 灌水Q群：782534512（欢迎来玩）

搬运于2025-08-24 21:55:16，当前版本为作者最后更新于2022-02-20 17:12:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

传送门 qwq

本题解使用 FHQ-Treap。

显然我们要把问题转化为平衡树擅长的序列问题。

首先你需要掌握“按照大小对平衡树进行分裂”，模板：P3391 【模板】文艺平衡树。这样分裂下来一棵树，其中序遍历就是其代表的序列。

初始序列为 $1,2,3,…,n$。聪明的你一定可以通过举例或是画图等方法发现，对于一次操作，给出 $R$，其实就是把序列的前 $R$ 个数截下来搬到序列末尾。$R$ 如果大于等于剩余牌的数量，要对这个数量取膜。显然正确性没有问题。

那么每次操作，我们按大小分裂出前 $R$ 个点，也就是平衡树中序遍历的前 $R$ 个点，也就是当前序列中前 $R$ 张牌的编号，然后将分裂的两颗树合并，注意由于是把这一段放到末尾，所以 merge 传参数的时候千万别写反。写反的话裂完原样合并你写个寂寞。这时候发一张牌，也就是序列的第一个数，也就是平衡树中序遍历的第一个数，所以直接按大小分裂出大小为 $1$ 的一棵树，编号即这张牌。然后根节点直接赋值为分出来的另一棵树的根，因为发完牌这个数我们就不要了。

$700000$ 的数据范围，数组别开小，出题人累死荷官。

#include<bits/stdc++.h>
using namespace std;
int read(){
	int ss=0,ww=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			ww=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		ss=ss*10+ch-'0';
		ch=getchar();
	}
	return ss*ww;
}
int n,m;
const int N=700100;
int root,cnt,ls[N],rs[N],sz[N],c[N];
int newnode(){
	cnt++;
	c[cnt]=rand();
	sz[cnt]=1;
	return cnt;
}
int x,y,z;
void upd(int r){
	sz[r]=sz[ls[r]]+sz[rs[r]]+1;
}
void split(int r,int k,int &x,int &y){
	if(!r){
		x=0;
		y=0;
		return;
	}
	if(sz[ls[r]]>=k){
		y=r;
		split(ls[r],k,x,ls[r]);
	}
	else{
		x=r;
		split(rs[r],k-sz[ls[r]]-1,rs[r],y);
	}
	upd(r);
}
int merge(int r1,int r2){
	if(!r1||!r2)
		return r1+r2;
	if(c[r1]<=c[r2]){
		rs[r1]=merge(rs[r1],r2);
		upd(r1);
		return r1;
	}
	else{
		ls[r2]=merge(r1,ls[r2]);
		upd(r2);
		return r2;
	}
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)
		root=merge(root,newnode());
	int rest=n;
	for(int i=1;i<=n;i++){
		int a;
		a=read();
		a%=rest;
		rest--;
		if(a){
			split(root,a,x,y);
			root=merge(y,x);
		}
		split(root,1,x,y);
		printf("%d\n",x);
		root=y;
	}
	return 0;
}