本来想把这题放在Splay学习笔记里的，但是这题卡了我一天，而且网上解题报告很少，所以我单独拿出来写一篇报告吧。

题意：给出一个无序序列，请用翻转的方法给它排序：翻转的起点依次递增，输出每次翻转的终点。比如3 4 5 1 6 2这个序列，最小的元素在4位置，第一遍排序的时候以1为起点4为终点转后为1 5 4 3 6 2；第二遍的时候最小的在位置6，则以2为起点6为终点转成1 2 6 3 4 5；第三遍最小的在4，旋转3 4；。。。。。。

解析：

        由于涉及到区间的翻转，所以用Splay会比较方便，用Splay树记录未最终定位的元素，中序遍历Splay树即可知道当前经过翻转后的序列，每排好一个元素，就把它从树里面删除。

        每次翻转的终点都是未排序的序列的最小元素，我们可以预处理下，把每个元素在树中的位置记录下来。然后把序列按值大小排序，依次处理每个元素。

        对于一个序列中的元素，它在Splay树中序序列里面的位置加上已排好序的元素个数就是翻转的终点。而元素在树中的位置已经记录下来了，我们只要把它Splay到根结点，统计它左子树的元素个数就是中序遍历序列在该元素左边的元素个数。

        pos(i)=i左边元素个数+已排好序的元素个数+1;

        由于i已经排好了序，把它删除即可。

        为了方便提取区间和删除，添加了一个开始端点和结束端点，因为翻转会把端点翻到左子树里面导致在统计左子树元素个数的时候令我蛋疼不已。最后不得已在节点里添加了一项记录该子树除端点以外的节点个数。如果各位网友有更好的办法，欢迎留言赐教，小弟不胜感激！

最后附上代码：

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

struct IN
{
	int val,pos;
}in[100001];

bool cmp(const IN &a,const IN &b)
{
	if(a.val==b.val)
		return a.pos<b.pos;
	return a.val<b.val;
}

struct Node
{
	Node *pre,*ch[2];//前驱结点，左右孩子
	bool rev;               //标记是否被翻转
	int size,val,rsz;     //子树大小,结点的值，子树除端点以外的大小
}*root,buf[100010],*null;

Node *rec[100010];
const int INF=1<<28;
int idx,N;

Node *addNode()
{
	Node *p;
	p=&buf[idx++];
	p->rsz=p->size=1;
	p->rev=false;
	p->ch[0]=p->ch[1]=p->pre=null;
	return p;
}

inline void UpdateSize(Node *p)
{
	p->size=p->ch[0]->size+p->ch[1]->size+1;
	p->rsz=p->ch[0]->rsz+p->ch[1]->rsz;
	if(p->val!=-1)p->rsz++;
}

inline void UpdateRev(Node *p)//更新处理翻转
{
	if(p==null||!p||!p->rev)return;
	swap(p->ch[0],p->ch[1]);
	if(p->ch[0]!=null)p->ch[0]->rev=!p->ch[0]->rev;
	if(p->ch[1]!=null)p->ch[1]->rev=!p->ch[1]->rev;
	p->rev=false;
}

void Init()
{
	idx=0;
	null=addNode();
	null->size=0;null->val=-1;null->rsz=0;
	root=addNode();                                //此处添加了两个端点
	root->ch[1]=addNode();root->val=-1;root->rsz=0;
	root->ch[1]->pre=root;root->ch[1]->val=-1;root->ch[1]->rsz=0;
	UpdateSize(root);
}

void Rotate(Node *x,int c)
{
	Node *y=x->pre;
	y->ch[!c]=x->ch[c];
	if(x->ch[c]!=null)
		x->ch[c]->pre=y;
	x->pre=y->pre;
	if(y->pre!=null)
		if(y->pre->ch[0]==y)
			y->pre->ch[0]=x;
		else
			y->pre->ch[1]=x;
	x->ch[c]=y;y->pre=x;
	if(y==root)root=x;
	UpdateSize(y);
}

void Splay(Node *x,Node *f)
{
	while(x->pre!=f)
	{
		Node *y=x->pre,*z=y->pre;
		UpdateRev(z);UpdateRev(y);UpdateRev(x);;
		if(x->pre->pre==f)
			Rotate(x,x->pre->ch[0]==x);
		else
		{
			if(z->ch[0]==y)
				if(y->ch[0]==x)
					Rotate(y,1),Rotate(x,1);
				else
					Rotate(x,0),Rotate(x,1);
			else
				if(y->ch[1]==x)
					Rotate(y,0),Rotate(x,0);
				else
					Rotate(x,1),Rotate(x,0);
		}
	}
	UpdateSize(x);
}

void Select(int kth,Node *f)
{
	int tmp;
	Node *t=root;
	while(1)
	{
		UpdateRev(t);
		tmp=t->ch[0]->size;
		if(tmp+1==kth)break;
		if(kth<=tmp)
			t=t->ch[0];
		else
		{
			kth-=tmp+1;
			t=t->ch[1];
		}
	}
	Splay(t,f);
}

Node *Build(int l,int r)
{
	if(l>r)return null;
	int mid=(l+r)>>1;
	Node *p=addNode();
	rec[mid]=p;p->val=in[mid].val;
	p->ch[0]=Build(l,mid-1);
	if(p->ch[0]!=null)
		p->ch[0]->pre=p;
	p->ch[1]=Build(mid+1,r);
	if(p->ch[1]!=null)
		p->ch[1]->pre=p;
	UpdateSize(p);
	return p;
}

void Delete()
{
	Node *oroot=root;
	root=root->ch[1];
	root->pre=null;
	Select(1,null);
	root->ch[0]=oroot->ch[0];
	root->ch[0]->pre=root;
	UpdateSize(root);
}

void Gao()
{
	for(int i=1;i<=N;i++)
		in[i].pos=i;
	sort(in+1,in+N+1,cmp);
	for(int i=1;i<=N;i++)
	{
		Splay(rec[in[i].pos],null);
		if(root->ch[0]!=null)
			root->ch[0]->rev=!root->ch[0]->rev;
		printf("%d",root->ch[0]->rsz+i);
		if(i!=N)putchar(' ');
		Delete();
	}
	puts("");
}

int main()
{
	while(scanf("%d",&N),N)
	{
		Init();
		for(int i=1;i<=N;i++)
			scanf("%d",&in[i].val);

		Node *troot=Build(1,N);
		root->ch[1]->ch[0]=troot;
		troot->pre=root->ch[1];
		UpdateSize(root->ch[1]);
		UpdateSize(root);
		Splay(root->ch[1],null);
		Gao();
	}
	return 0;
}

• 相关文章