poj-3580 SuperMemo[splay tree]

学了splay 后 撸的第一道题。

是看了大神的教学，引用了大神的核心代码才会的:splay tree 学习

刚开始没注意：使用一个节点你需要把他的标记先下压。提供了好多次wa。

/*题意：给一个数组，有6种操作：

(1)add  x y d  ： [x,y]中所有数加d

----x-1
---------y+1
---[x,y]
给y-1的左子树加上+d 标记

(2)reverse x y:
[x,y]区间翻转

---- x-1
-------------y+1
-------[x,y]
给y-1的左子树加上翻转标记(即左右子树概念上要互换，去标记就执行这步操作)

(3)revolve x y t:
[x,y]循环右移t位，t可取任意整数
------x-1
-------------------y+1
-------------y-t
-----[x,y-t-1]--[y-t+1,y]
上两层操作同上，y-t splay到 y-1的左子树处
-----x-1
---------------y+1
------------y-t
-----[x,y-t-1]    p2=[y-t+1,y]
断开y-t 右子树,将x splay到y-t的位置
-----x-1
---------------y+1
------------x
- p2=[y-t+1,y]-----[x+1,y-t-1] 
中序遍历为循环移位顺序

(4)insert  x v:
在第x个数后面插入P
-----x
-------x+1
可以知道 x-1左子树为Null插入p
-----x
--------x+1
-----p

(5)delete  x : 删除第x个数
-----x-1
---------x+1
------x
删除x

(6)min  x y : 求区间[x,y]的最小值
----x-1
--------y+1
----[x,y]

结尾都把更改的节点翻转到树根

求值即可
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define Max_N 100008
#define INF 0x3f3f3f3f
#define ZIG 1
#define ZAG 0
#define find_min(a,b) a>b?b:a
using namespace std;
struct  sp_node{
	// pre 表示指向父亲的指针
	//ch[0],ch[1]分别是左儿子和右儿子
	sp_node *pre,*ch[2];
	int val,lazy,Min,size;
	//lazy add()的延迟标记 size表示节点的子树有多少节点
	bool isRev;//翻转的延迟标记
};
class sp_tree
{
public:
	void init(int *input,int n);//根据输入序列进行初始化
	void add(int x,int y,int d);//[x,y]中所有数加d
	void reverse(int x,int y);//[x,y]区间翻转
	void revolve(int x,int y,int t);//[x,y]循环右移t位，t可取任意整数
	void insert(int x,int v);//在第x个数后面插入P
	void Delete(int x);//删除第x个数
	int get_min(int x,int y);//求区间[x,y]的最小值
private:
	sp_node nstack[Max_N*4];
	int scnt;
	sp_node *root;
	sp_node *get_sp_node();//从栈里得到到一个节点;
	sp_node *find_sp_node(int x);//寻找编号为x的节点
	sp_node *create_sp_tree(int *input,int l,int r);//递归创造一个平衡二叉排序树
	void rotate(sp_node *x,int c);//旋转操作，c=0 表示左旋，c=1 表示右旋 
	void splay(sp_node *,sp_node *f);// Splay 操作，表示把结点x 转到结点f 的下面 
	void push_down(sp_node *x);//把x标记下传
	void update(sp_node *x);//更新维护 x节点
	void select(int k,sp_node *f);// 找到处在中序遍历第k 个结点，并将其旋转到结点f 的下面
	void infix_print(sp_node *root)//输出查看
	{
		if(!root)
			return;
		infix_print(root->ch[0]);
		//printf("val:%d size:%d min:%d lazy:%d isRev:%d\n",
		//	root->val,root->size,root->Min,root->lazy,root->isRev);
		printf("%d ",root->val);
		infix_print(root->ch[1]);
	}
};
sp_node *sp_tree::get_sp_node()
{
	sp_node *sp=nstack+scnt;
	sp->ch[0]=sp->ch[1]=sp->pre=NULL;
	sp->Min=INF,sp->isRev=0,sp->lazy=0,sp->size=0;
	++scnt;
	return sp;
}
sp_node *sp_tree::create_sp_tree(int *input,int l,int r)
{
	if(l>r)
		return NULL;
	int mid=(l+r)/2;
	sp_node *spn=get_sp_node();
	spn->ch[0]=create_sp_tree(input,l,mid-1);
	spn->ch[1]=create_sp_tree(input,mid+1,r);
	spn->val=input[mid],spn->size=r-l+1,spn->Min=input[mid];
	if(spn->ch[0])
	{
		spn->Min=find_min(spn->Min,spn->ch[0]->Min);
		spn->ch[0]->pre=spn;
	}
	if(spn->ch[1])
	{
		spn->Min=find_min(spn->Min,spn->ch[1]->Min);
		spn->ch[1]->pre=spn;
	}
	return spn;
}
/*大神模板开始*/
void sp_tree::rotate(sp_node *x,int c)
{// 旋转操作，c=0 表示左旋，c=1 表示右旋
	sp_node *y=x->pre;
	push_down(y),push_down(x);
	//先将Y 结点的标记向下传递（因为Y 在上面），再把X 的标记向下传递
	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,update(y);// 维护Y 结点
	if(y==root) root=x; //root 表示整棵树的根结点 
}
void sp_tree::splay(sp_node *x,sp_node *f)
{//特别地，转到根就是转到空结点Null 的下面
	for(push_down(x);x->pre!=f;) // 一开始就将X 的标记下传
		if(x->pre->pre==f) // 父结点的父亲即为f，执行单旋转 
			if(x->pre->ch[0]==x) rotate(x,ZIG);
			else rotate(x,ZAG);
		else 
		{
			sp_node *y=x->pre,*z=y->pre;
			if(z->ch[0]==y)
				if(y->ch[0]==x)
					rotate(y,ZIG),rotate(x,ZIG); // 一字形旋转  
				else rotate(x,ZAG),rotate(x,ZIG); // 之字形旋转  
			else if(y->ch[1]==x)
				rotate(y,ZAG),rotate(x,ZAG); // 一字形旋转   
			else rotate(x,ZIG),rotate(x,ZAG); // 之字形旋转  
		}
	update(x);// 最后再维护X 结点 
}
void sp_tree::select(int k,sp_node *f)
{
	int tmp;
	sp_node *t;
	for(t=root;;)
	{
		//因为每次都要标记下压，所以不用担心翻转问题
		push_down(t); // 由于要访问t 的子结点，将标记下传
		if(t->ch[0])
			tmp=t->ch[0]->size;  // 得到t 左子树的大小
		else tmp=0;
		if(k==tmp) break;
		if(k<tmp)// 第k 个结点在t 左边，向左走  
			t=t->ch[0];
		// 否则在右边，而且在右子树中，这个结点不再是第k 个  
		else k-=tmp+1,t=t->ch[1];
	}
	splay(t,f);
}
/*大神模板结束*/
/*看大神的模板，下压标记的操作和更新节点很经典,就是每次进行操作前都把标记下压（当前节点把延迟的
操作给解决掉，延迟标记传递给儿子），这样就不用考虑当前结点的标记问题.
也就是说参与splay的节点都解决了延迟标记和更新了信息
*/
void sp_tree::push_down(sp_node *x)
{/*push_down主要是应用区间树的延迟标记技术中。
	x拥有的标记表示以x为根的树有 标记的操作，但没有做
	
	让x执行标记的操作和下压标记
	*/
	if(!x)
		return;
	if(x->lazy)
	{
		int w=x->lazy;
		x->val+=w;
		if(x->ch[0])
			x->ch[0]->lazy+=w,x->ch[0]->Min+=w;
		if(x->ch[1])
			x->ch[1]->lazy+=w,x->ch[1]->Min+=w;
		x->lazy=0;
	}
	if(x->isRev)
	{
		sp_node *t=x->ch[0];
		x->ch[0]=x->ch[1],x->ch[1]=t,x->isRev=0;
		if(x->ch[0]) x->ch[0]->isRev^=1;
		if(x->ch[1]) x->ch[1]->isRev^=1;
	}
}
void sp_tree::update(sp_node *x)
{
	if(!x)
		return;
	x->size=1,x->Min=x->val;
	if(x->ch[0])
	{
		x->Min=find_min(x->Min,x->ch[0]->Min);
		x->size+=x->ch[0]->size;
	}
	if(x->ch[1])
	{
		x->Min=find_min(x->Min,x->ch[1]->Min);
		x->size+=x->ch[1]->size;
	}
}
void sp_tree::init(int *input,int n)
{
	input[0]=input[n+1]=INF;
	scnt=0;
	root=create_sp_tree(input,0,n+1);
}
void sp_tree::add(int x,int y,int d)
{
	/*
	(1)add  x y d  ： [x,y]中所有数加d
	----x-1
	---------y+1
	---[x,y]
	给y-1的左子树加上+d 标记
	*/
	sp_node *sp;
	select(x-1,NULL),select(y+1,root);
	sp=root->ch[1],push_down(sp);
	sp=sp->ch[0],sp->lazy+=d,push_down(sp);
	splay(sp,NULL);
}
void sp_tree::reverse(int x,int y)
{
	/*
	(2)reverse x y:
	[x,y]区间翻转
	---- x-1
	-------------y+1
	-------[x,y]
	给y-1的左子树加上翻转标记*/
	sp_node *sp;
	select(x-1,NULL),select(y+1,root);
	sp=root->ch[1],push_down(sp);
	sp=sp->ch[0],push_down(sp),sp->isRev^=1;
	splay(sp,NULL);
}
void sp_tree::revolve(int x,int y,int t)
{
	/*
	[x,y]循环右移t位，t可取任意整数
	------x-1
	-------------------y+1
	-------------y-t
	-----[x,y-t-1]--[y-t+1,y]
	上两层操作同上，y-t splay到 y-1的左子树处
	-----x-1
	---------------y+1
	------------y-t
	-----[x,y-t-1]    p2=[y-t+1,y]
	断开y-t 右子树,将x splay到y-t的位置
	-----x-1
	---------------y+1
	------------x
	- p2=[y-t+1,y]-----[x+1,y-t-1] 
	中序遍历为循环移位顺序
	*/
	int tn=y-x+1;
    t=(t%tn+tn)%tn;
    if(x==y||t==0)
    	return;
	sp_node *p1,*p2;
	select(x-1,NULL),select(y+1,root),select(y-t,root->ch[1]);
	p1=root->ch[1]->ch[0],push_down(p1);
	p2=p1->ch[1],p1->ch[1]=NULL;
	select(x,root->ch[1]);
	p1=root->ch[1]->ch[0],push_down(p1);
	p1->ch[0]=p2,p2->pre=p1;
	splay(p2,NULL);
}
void sp_tree::insert(int x,int v)
{	
/*
	在第x个数后面插入P
	-----x
	-------x+1
	可以知道 x-1左子树为Null插入p
	-----x
	--------x+1
	-----p
*/	sp_node *sp;
	select(x,NULL),select(x+1,root);
	sp=root->ch[1],push_down(sp);
	sp_node *p=get_sp_node();
	p->val=v;
	sp->ch[0]=p,p->pre=sp;
	splay(p,NULL);
}
void sp_tree::Delete(int x)
{
	/*
	delete  x : 删除第x个数
	-----x-1
	---------x+1
	------x
	删除x
	*/sp_node *sp;
	select(x-1,NULL),select(x+1,root);
	sp=root->ch[1],push_down(sp);
	sp->ch[0]=NULL;
	splay(sp,NULL);

}
int sp_tree::get_min(int x,int y)
{
	/*
	min  x y : 求区间[x,y]的最小值
	----x-1
	--------y+1
	----[x,y]
	*/sp_node *sp;
	select(x-1,NULL),select(y+1,root);
	//infix_print(root);
	sp=root->ch[1],push_down(sp);
	sp=sp->ch[0],push_down(sp);
	int res=sp->Min;
	splay(sp,NULL);
	return res;
}
int input[Max_N];
char choice[6][10]={"ADD","REVERSE","REVOLVE","INSERT","DELETE","MIN"};
sp_tree spt;
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		for(int i=1;i<=n;++i)
			scanf("%d",input+i);
		spt.init(input,n);
		int m;
		scanf("%d",&m);
		char str[10];
		int x,y,d;
		while(m--)
		{
			scanf("%s",str);
			if(!strcmp(choice[0],str))
			{
				scanf("%d %d %d",&x,&y,&d);
				spt.add(x,y,d);
			}
			else if(!strcmp(choice[1],str))
			{
				scanf("%d %d",&x,&y);
				spt.reverse(x,y);
			}
			else if(!strcmp(choice[2],str))
			{
				scanf("%d %d %d",&x,&y,&d);
				spt.revolve(x,y,d);
			}
			else if(!strcmp(choice[3],str))
			{
				scanf("%d %d",&x,&d);
				spt.insert(x,d);
			}
			else if(!strcmp(choice[4],str))
			{
				scanf("%d %d",&x,&d);
				spt.Delete(x);
			}
			else if(!strcmp(choice[5],str))
			{
				scanf("%d %d",&x,&y);
				printf("%d\n",spt.get_min(x,y));
			}
		}
	}
	return 0;
}