BZOJ 1552 [Cerc2007]robotic sort

题目大意

给你一个序列，每次执行：选出序列中第i小的数j,之后翻转序列[i,j].

反转操作Splay最拿手……

注意每次得找到第i大的数的编号，之后提取的是这个编号+1那个数作为右端点，其他提取方法都不行……

还有这题会PE.

#include <cstdio>
#include <algorithm>
using namespace std;

#define N 100010

struct num{int v,id;}a[N],p[N];

bool cmp(num tx,num ty) {return tx.v==ty.v?tx.id<ty.id:tx.v<ty.v;}

int n,rt,c[2][N],fa[N],siz[N];

bool rev[N];

inline void pushup(int pos) {siz[pos]=siz[c[0][pos]]+siz[c[1][pos]]+1;}

inline void pushdown(int pos)
{
	if(rev[pos])
	{
		int tl=c[0][pos],tr=c[1][pos];
		swap(c[0][tl],c[1][tl]),swap(c[0][tr],c[1][tr]);
		rev[tl]^=1,rev[tr]^=1,rev[pos]=0;
	}
}

inline int RI()
{
	int ret=0;
	char tmp=getchar();
	while(tmp<'0'||tmp>'9') tmp=getchar();
	while(tmp>='0'&&tmp<='9') ret=ret*10+tmp-'0',tmp=getchar();
	return ret;
}

inline void rotate(int &tg,int tx)
{
	int ty=fa[tx],tz=fa[ty],tl=(c[1][ty]==tx),tr=tl^1;
	if(ty==tg) tg=tx;
	else c[c[1][tz]==ty][tz]=tx;
	fa[tx]=tz,fa[ty]=tx;
	fa[c[tr][tx]]=ty,c[tl][ty]=c[tr][tx],c[tr][tx]=ty;
	pushup(ty),pushup(tx);
}

inline void splay(int &tg,int tx)
{
	while(tx!=tg)
	{
		int ty=fa[tx],tz=fa[ty];
		if(ty!=tg)
		{
			if((c[1][ty]==tx)^(c[1][tz]==ty)) rotate(tg,tx);
			else rotate(tg,ty);
		}
		rotate(tg,tx);
	}
}

int getrank(int tg)
{
	if(fa[tg])
	{
		int tmp=getrank(fa[tg]);
		pushdown(tg);
		if(c[1][fa[tg]]==tg) return tmp+siz[c[0][tg]]+1;
		else return tmp-1-siz[c[1][tg]];
	}
	else return siz[c[0][tg]]+1;
}

int getpos(int pos,int tg)
{
	pushdown(pos);
	if(tg<=siz[c[0][pos]]) return getpos(c[0][pos],tg);
	if(tg>siz[c[0][pos]]+1) return getpos(c[1][pos],tg-siz[c[0][pos]]-1);
	return pos;
}

int build(int l,int r)
{
	if(l>r) return 0;
	int mid=(l+r)>>1;
	c[0][mid]=build(l,mid-1),fa[c[0][mid]]=mid;
	c[1][mid]=build(mid+1,r),fa[c[1][mid]]=mid;
	pushup(mid);
	return mid;
}

int main()
{
	n=RI();
	for(int i=1;i<=n;++i) a[i].v=RI(),a[i].id=i,p[i+1].v=a[i].v;
	rt=build(1,n+2);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;++i)
	{
		splay(rt,getpos(rt,i));
		int tmp=getrank(a[i].id+1);
		printf("%d%c",tmp-1,i==n?'\n':' ');
		splay(c[1][rt],getpos(rt,tmp+1));
		swap(c[0][c[0][c[1][rt]]],c[1][c[0][c[1][rt]]]);
		rev[c[0][c[1][rt]]]^=1;
	}
}