【BZOJ3506】排序机械臂（Splay）

时间：2020-12-26 14:39:07

【BZOJ3506】排序机械臂（Splay）

题面

神TMBZOJ没有题面，感谢SYC的题面

洛谷的题面也不错

题解

对于每次旋转的物体

显然可以预处理出来

现在只要模拟旋转操作就行了

至于在哪里放标记的问题

我只在第K大放会鬼。。

所以在Splay里面也放了一次（和LCT一样的）

然而我每次都把排到了正确位置的元素直接给删掉了。。。

所以跑的很慢很慢。。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 120000

#define lson (t[x].ch[0])

#define rson (t[x].ch[1])

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

struct Node

{

	int ch[2],ff;

	int v,size;

	int rev;

}t[MAX];

int root,n;

int S[MAX],top;

void pushup(int x)

{

	if(!x)return;

	t[x].size=t[lson].size+t[rson].size+1;

}

void rotate(int x)

{

	int y=t[x].ff,z=t[y].ff;

	int k=t[y].ch[1]==x;

	if(z)t[z].ch[t[z].ch[1]==y]=x;t[x].ff=z;

	t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].ff=y;

	t[x].ch[k^1]=y;t[y].ff=x;

	pushup(y);pushup(x);

}

void putrev(int x)

{

	swap(lson,rson);

	t[x].rev^=1;

}

void pushdown(int x)

{

	if(!t[x].rev)return;

	t[x].rev^=1;

	if(lson)putrev(lson);

	if(rson)putrev(rson);

}

void Splay(int x,int goal)

{

	S[top=1]=x;

	for(int i=x;i!=root;i=t[i].ff)S[++top]=t[i].ff;

	while(top)pushdown(S[top--]);

	while(t[x].ff!=goal)

	{

		int y=t[x].ff,z=t[y].ff;

		if(z!=goal)

			(t[y].ch[1]==x)^(t[z].ch[1]==y)?rotate(x):rotate(y);

		rotate(x);

	}

	if(!goal)root=x;

}

int Build(int l,int r)

{

	if(l>r)return 0;

	int mid=(l+r)>>1;

	t[mid].ch[0]=Build(l,mid-1);

	t[mid].ch[1]=Build(mid+1,r);

	t[t[mid].ch[0]].ff=t[t[mid].ch[1]].ff=mid;

	pushup(mid);

	return mid;

}

int Kth(int k)

{

	int x=root;

	while(233)

	{

		if(t[x].rev)pushdown(x);

		if(t[lson].size+1>=k)

		{

			if(t[lson].size+1==k)return x;

			else x=lson;

		}

		else k-=t[lson].size+1,x=rson;

	}

	return 0;

}

int Rank(int x)//查找x的排名

{

	Splay(x,0);

	return t[lson].size+1;

}

void Delete(int x)//删除节点x

{

	int tt=Rank(x);

	int L=Kth(tt-1);

	int R=Kth(tt+1);

	Splay(L,0);Splay(R,L);

	t[R].ch[0]=0;

	pushup(R);pushup(L);

}

void Outp(int x)

{

	if(lson)Outp(lson);

	printf("%d ",t[x].v);

	if(rson)Outp(rson);

}

pair<int,int> w[MAX];

int main()

{

	t[0].v=1e9;

	n=read();

	for(int i=2;i<=n+1;++i)t[i].v=read(),w[i-1]=make_pair(t[i].v,i);

	sort(&w[1],&w[n+1]);

	t[1].v=t[n+2].v=1e9;

	root=Build(1,n+2);

	for(int i=1;i<=n;++i)

	{

		int pp=w[i].second;

		int gg=Rank(pp);

		printf("%d ",gg-2+i);

		Splay(1,0);

		Splay(pp,1);

		if(t[pp].ch[0])putrev(t[pp].ch[0]);

		Delete(pp);

	}

	return 0;

}

/*

9

1 3 2 3 3 2 1 2 1

*/

相关文章