BZOJ 1552: [Cerc2007]robotic sort/3506: [Cqoi2014]排序机械臂 splay

1552: [Cerc2007]robotic sort

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1273  Solved: 488
[Submit][Status][Discuss]

Description

Input

输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。

第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。

Output

输出共一行，N个用空格隔开的正整数P1,P2,P3…Pn，Pi表示第i次操作前第i小的物品所在的位置。 

注意：如果第i次操作前，第i小的物品己经在正确的位置Pi上，我们将区间[Pi,Pi]反转(单个物品)。

Sample Input

6
3 4 5 1 6 2

Sample Output

4 6 4 5 6 6

发现自己又不会写splay了 GG

这题很水啊。。。我竟然硬是搞了两个小时。。。

只需要维护子树内权值最小的点的标号就好了

最开始打挂 然后狂调 最后越调越乱

无奈的重构代码

最后 这成为了我有史以来写的最好的一棵splay

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;

typedef long long ll;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}

void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}

const int N=100100,inf=0X3f3f3f3f;

struct node{int val,pos;friend bool operator <(const node &x,const node &y){return x.val==y.val?x.pos<y.pos:x.val<y.val;}}p[N];
inline bool cmp(const node &x,const node &y){return x.pos<y.pos;}

int n;
int root,ch[N][2],fa[N],V[N],mn[N],size[N];
bool rev[N];
int pos[N];
inline void pushup(int k)
{
	size[k]=size[ch[k][0]]+size[ch[k][1]]+1;
	mn[k]=k;
	if(ch[k][0]&&V[mn[ch[k][0]]]<V[mn[k]])mn[k]=mn[ch[k][0]];
	if(ch[k][1]&&V[mn[ch[k][1]]]<V[mn[k]])mn[k]=mn[ch[k][1]];
}

inline void pushdown(int k)
{
	if(rev[k])
	{
		rev[k]=0;
		swap(ch[k][0],ch[k][1]);
		rev[ch[k][0]]^=1;rev[ch[k][1]]^=1;
	}
}

inline void getdown(int k)
{if(fa[k])getdown(fa[k]);pushdown(k);}

int build(int l,int r,int pre)
{
	if(l>r)return 0;
	int mid=(l+r)>>1;
	fa[mid]=pre;
	V[mid]=p[mid].val;
	ch[mid][0]=build(l,mid-1,mid);
	ch[mid][1]=build(mid+1,r,mid);
	pushup(mid);
	return mid;
}

inline int find(int rk)
{
	int k=root;
	while(rk)
	{
		pushdown(k);
		if(size[ch[k][0]]>=rk)k=ch[k][0];
		else if(size[ch[k][0]]+1<rk)rk-=size[ch[k][0]]+1,k=ch[k][1];
		else return k;
	}
}

inline void rotate(int x,int &k)
{
	int y=fa[x],z=fa[y],l,r;
	l=(ch[y][1]==x);r=l^1;
	y==k?k=x:ch[z][ch[z][1]==y]=x;
	fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;
	ch[y][l]=ch[x][r];ch[x][r]=y;
	pushup(y);pushup(x);
}

void splay(int x,int &k)
{
	getdown(x);
	int y,z;
	while(x!=k)
	{
		y=fa[x],z=fa[y];
		if(y!=k)
		{
			if((ch[y][0]==x)^(ch[z][0]==y))rotate(x,k);
			else rotate(y,k);
		}
		rotate(x,k);
	}
}

int query_mn(int x,int y)
{
	x=find(x);y=find(y+2);
	splay(x,root);splay(y,ch[x][1]);
	return mn[ch[y][0]];
}

void rever(int x,int y)
{
	x=find(x),y=find(y+2);
	splay(x,root);splay(y,ch[x][1]);
	rev[ch[y][0]]^=1;
}

int main()
{
	n=read();
	register int i,x;
	p[1].val=p[n+2].val=inf;
	for(i=2;i<=n+1;++i)p[i].val=read(),p[i].pos=i;
	sort(p+2,p+2+n);
	for(i=2;i<=n+1;++i)p[i].val=i;
	sort(p+2,p+2+n,cmp);
	root=build(1,n+2,0);
	
	for(i=1;i<=n;++i)
	{
		x=query_mn(i,n);
		splay(x,root);
		print(size[ch[x][0]]);
		if(i^n)putchar(' ');
		rever(i,size[ch[x][0]]);
	}
	puts("");return 0;
}
/*
6
3 4 5 1 6 2

4 6 4 5 6 6
*/