[SHOI2013]发牌 解题报告

[SHOI2013]发牌

题意

对一个\(1\sim n(n\le 7\times 10^5)\)的环，指标最开始在\(1\)，每次删去顺时针往后第\(d_i\)个元素，指标移到下一个位置。要求输出每次删去元素的标号。

---

看了沙茶数据范围，我就放弃了平衡树，毕竟我这种人丑常数大的选手？

然后开始思考线段树或者树状数组，yy了好一会儿才想出一个沙茶的做法，写了以后发现题解好像没有我这么写的，就来口胡一下。

在线段树上维护每个点左边还有多少个元素存在。

每次询问的时候，有一个上次开始的删去的位置\(s\)(初始为\(0\))，然后统计一下\(s\)前面有多少个元素，判断这次删掉的是在\(s\)左边还是右边。

假设每次输入的是\(d\)，如果在\(s\)左边，就\(d-\)右边元素个数，在右边就\(d+\)左边元素个数，然后直接在线段树上二分找就可以了。

---

Code:

#include <cstdio>

#include <cctype>

#include <algorithm>

using std::max;

const int N=7e5+10;

int read()

{

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

int sum[N],n,s;

void add(int x){while(x<=n)++sum[x],x+=x&-x;}

int ask(int x){int ret=0;while(x)ret+=sum[x],x-=x&-x;return ret;}

int mx[N<<2],tag[N<<2];

#define ls id<<1

#define rs id<<1|1

void build(int id,int l,int r)

{

	mx[id]=r;

	if(l==r)return;

	int mid=l+r>>1;

	build(ls,l,mid),build(rs,mid+1,r);

}

void pushdown(int id)

{

	if(tag[id])

	{

		mx[ls]+=tag[id],mx[rs]+=tag[id];

		tag[ls]+=tag[id],tag[rs]+=tag[id];

		tag[id]=0;

	}

}

void query(int id,int l,int r,int k)

{

	if(l==r) {printf("%d\n",s=l),mx[id]=0,add(l);return;}

	pushdown(id);

	int mid=l+r>>1;

	if(mx[ls]>=k) query(ls,l,mid,k);

	else query(rs,mid+1,r,k);

}

void change(int id,int l,int r,int p)

{

	if(l>=p){--mx[id],--tag[id];return;}

	pushdown(id);

	int mid=l+r>>1;

	if(p<=mid) change(ls,l,mid,p);

	change(rs,mid+1,r,p);

	mx[id]=max(mx[ls],mx[rs]);

}

int main()

{

	n=read();

	build(1,1,n);

	for(int rig,lef,r,i=n;i;i--)

	{

		r=read()%i;

		lef=s-ask(s);//左边个数

		rig=i-lef;//右边个数

		if(rig<=r) r-=rig;//左边

		else r+=lef;

		query(1,1,n,r+1);

		change(1,1,n,s);

	}

	return 0;

}

---

2019.2.12