[CQOI 2014] 排序机械臂

看完此题数据范围n<=100000，就知道与模拟无缘了（不知道是脑残还是怎样，第一次做的时候由于只剩下半个小时，于是匆匆写了个模拟，然后光荣的爆0了，原因很简单，我把题目看错了T_T）

就是这句话：如果有高度相同的物品，必须保证他们排序后与初始的相对位置关系相同。

被样例2骗了，SB的写了一个错误的DP，然后由于splay太长时间没写，所以……

对于这个限制条件，我给每个点加上了时间标记dnf（这当然不是tarjan……随手写写而已）

然后加上三个与DP相关的域：mi,ti,pos，分别表示当前区间可以取到的最小值、该最小值所对应的时间戳，要达到该最小值该怎么走(pos=0时为本身，pos=1时向左走，pos=2时向右走)，然后DP方程就可以随便写了，另外涉及反转区间加上rev域，这个真是做烂了，没什么好说的。

好不容易把splay写完了，结果TLE（我开始质疑这台电脑了），无奈之下，将初始的链建成一棵二叉树，还是TLE，然后只好到bzoj上提交，两份代码都AC了，相差几十毫秒（坑爹啊！）

这一次偷懒没写自顶向下的splay，写的是自底向上的，感觉WJMZBMR的思路太神奇了，splay那么短（十分感动……）

其他就没有什么好说了，上代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <map>
#define setc(x,s,d) (p[c[x][d]=s]=x,update(x))
#define root(x) (!p[x])
#define ch(x) (c[p[x]][1]==x)
#define _rev(x) (rev[x]^=1)
#define MaxN 100010
using namespace std;
const int INF=~0U>>2;
int n,t,x,ans;
int a[MaxN],c[MaxN][2],p[MaxN],sz[MaxN];
int pos[MaxN],mi[MaxN],dfn[MaxN],ti[MaxN];
bool rev[MaxN];
map<int,int> m;
map<int,int>::iterator iter;
inline void push(const int &x)
{
	if(!x) return;
	if(rev[x])
	{
		swap(c[x][0],c[x][1]);
		pos[x]=3-pos[x];
		pos[x]%=3;
		if(c[x][0]) _rev(c[x][0]);
		if(c[x][1]) _rev(c[x][1]);
		rev[x]=0;
	}
}
inline void update(const int &x)
{
	if(!x) return;
	sz[x]=sz[c[x][0]]+1+sz[c[x][1]];
	mi[x]=a[x],pos[x]=0,ti[x]=dfn[x];
	for(int i=0;i<2;i++)
		if(mi[c[x][i]]<mi[x])
			mi[x]=mi[c[x][i]],
			pos[x]=i+1,
			ti[x]=ti[c[x][i]];
		else if(mi[c[x][i]]==mi[x])
			if(ti[c[x][i]]<ti[x])
				pos[x]=i+1,
				ti[x]=ti[c[x][i]];
}
inline void rorate(const int &x)
{
	int f=p[x];
	bool d=ch(x);
	setc(f,c[x][!d],d);
	if(root(f)) p[x]=p[f];
	else setc(p[f],x,ch(f));
	setc(x,f,!d);
}
inline int find(int &t)
{
	int ans=0;
	push(t);
	while(pos[t])
	{
		if(pos[t]-1) ans+=sz[c[t][0]]+1;
		t=c[t][pos[t]-1];
		push(t);
	}
	return ans+sz[c[t][0]];
}
inline void splay(int rt,int x)
{
	while(p[x]!=rt)
		if(p[p[x]]==rt)
			rorate(x);
		else if(ch(x)==ch(p[x]))
			rorate(p[x]),rorate(x);
		else if(p[p[x]]!=rt)
			rorate(x),rorate(x);
		else rorate(x);
}
inline int side(int x)
{
	push(x);
	while(c[x][0])
		x=c[x][0],
		push(x);
	return x;
}
inline void work()
{
	for(int i=1;i<n;i++)
	{
		x=t;
		ans=find(x);
		printf("%d ",ans+i);
		splay(0,x);
		if(c[x][1])
			splay(x,side(c[x][1])),
			t=c[x][1],
			setc(t,c[x][0],0),
			_rev(c[x][0]);
		else
			t=c[x][0],
			_rev(t);
		p[t]=0;
	}
	printf("%d\n",n);
}

int build(int l,int r)
{
	if(l>r) return 0;
	int m=(l+r)>>1;
	if(l!=r)
		p[c[m][0]=build(l,m-1)]=m,
		p[c[m][1]=build(m+1,r)]=m;
	update(m);
	return m;
}

inline void init()
{
	mi[0]=dfn[0]=ti[0]=INF;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		iter=m.find(a[i]);
		if(iter==m.end())
			m.insert(make_pair(a[i],0));
		else dfn[i]=++(iter->second);
//		setc(i,i-1,0);
	}
	t=build(1,n);
//	t=n;
}
int main()
{
//	freopen("sort.in","r",stdin);
//	freopen("sort.out","w",stdout);
	init();
	work();
	return 0;
}

[CQOI 2014] 排序机械臂,布布扣,bubuko.com

[CQOI 2014] 排序机械臂

原文：http://blog.csdn.net/doveccl/article/details/23128321