P3988 [SHOI2013]发牌

题目

P3988 [SHOI2013]发牌

做法

我们切牌时的状态：

手玩几次后我们发现切\(K\)次牌就是求堆顶一下的\(K+1\)大值，套上主席树就好了

My complete code

#include<cstdio>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<iostream>

using namespace std;

typedef long long LL;

const LL maxn=2000000;

inline LL Read(){

	LL x(0),f(1);char c=getchar();

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

	return x*f;

}

LL n,m,top,nod,root;

struct Tree{

	LL son[2],sum;

}T[maxn];

inline void Build(LL &now,LL l,LL r){

	now=++nod;

	T[now].sum=r-l+1;

	if(l==r)

	    return;

	LL mid(l+r>>1);

	Build(T[now].son[0],l,mid);

	Build(T[now].son[1],mid+1,r);

}

inline LL Query(LL now,LL l,LL r,LL K){

	--T[now].sum;

	if(l==r)

	    return l;

	LL mid(l+r>>1);

	if(T[T[now].son[0]].sum>=K)

	    return Query(T[now].son[0],l,mid,K);

	else

	    return Query(T[now].son[1],mid+1,r,K-T[T[now].son[0]].sum);

}

int main(){

	m=n=Read(),

	Build(root,1,n),

	top=1;

	while(m--){

		LL r(Read());

		top=(top+r)%(m+1);

		if(top==0) top=(m+1);

		LL now(Query(root,1,n,top));

		printf("%lld\n",now);

	}

}/*

*/