bzoj1251 序列終結者

bzoj1251 序列終結者

Description

網上有許多題，就是給定一個序列，要你支持幾種操作：A、B、C、D。一看另一道題，又是一個序列 要支持幾種操作：D、C、B、A。尤其是我們這裡的某人，出模擬試題，居然還出了一道這樣的，真是沒技術含量……這樣 我也出一道題，我出這一道的目的是為了讓大家以後做這種題目有一個“庫”可以依靠，沒有什麼其他的意思。這道題目 就叫序列終結者吧。 【問題描述】 給定一個長度為N的序列，每個序列的元素是一個整數（廢話）。要支持以下三種操作： 1. 將[L,R]這個區間內的所有數加上V。 2. 將[L,R]這個區間翻轉，比如1 2 3 4變成4 3 2 1。 3. 求[L,R]這個區間中的最大值。 最開始所有元素都是0。

Input

第一行兩個整數N，M。M為操作個數。 以下M行，每行最多四個整數，依次為K，L，R，V。K表示是第幾種操作，如果不是第1種操作則K後面只有兩個數。

Output

對於每個第3種操作，給出正確的回答。

Sample Input

Sample Output

HINT

Source

Splay

每次進行序列操作時，把l-1旋轉到根，把r+1旋轉到根的右兒子，r+1的左子樹就是整個區間[l,r]。

我們可以用Splay的每個節點記錄該節點對應子樹的信息，那麼每次詢問只要輸出r+1的左子樹中的最大值，即代碼中的mx[t[y][0]]。

為了避免Splay中有節點0，我們將所有節點的編號加1。又因為要旋轉l-1和r+1，所以在Splay插入節點為1到n+2。(原因顯然…大家自己腦補)

這道題用Splay的提根操作達到了區間操作的目的，方法很巧妙。

另外我覺得這道題有幾點需要注意：

①要理解Splay中節點的含義以及節點所記錄的信息。

②區間的翻轉操作很巧妙，只需要將標記下傳並且交換左右子樹，並不需要修改節點的max和size。

③每次find操作都要pushdown，這樣就可以保證節點x到根的路徑上所有點都被更新，便於之後的旋轉操作。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define LL long long
#define pa pair
#define MAXN 50005
#define INF 1000000000
using namespace std;
int n,m,rt=0,tot=0;
int a[MAXN],fa[MAXN],t[MAXN][2],mx[MAXN],tag[MAXN],size[MAXN];
bool rev[MAXN];
inline int read()
{
	int ret=0,flag=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') flag=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*flag;
}
inline void pushup(int k)
{
	int l=t[k][0],r=t[k][1];
	mx[k]=max(max(mx[l],mx[r]),a[k]);
	size[k]=size[l]+size[r]+1;
}
inline void pushdown(int k)
{
	int l=t[k][0],r=t[k][1],tg=tag[k];
	if (tg)
	{
		tag[k]=0;
		if (l){tag[l]+=tg;mx[l]+=tg;a[l]+=tg;}
		if (r){tag[r]+=tg;mx[r]+=tg;a[r]+=tg;}
	}
	if (rev[k])
	{
		rev[k]=0;
		rev[l]^=1;rev[r]^=1;
		swap(t[k][0],t[k][1]);
	}
}
inline void rotate(int &k,int x)
{
	int y=fa[x],z=fa[y],l,r;
	if (t[y][0]==x) l=0;else l=1;r=l^1;
	if (k==y) k=x;
	else{if (t[z][0]==y) t[z][0]=x;else t[z][1]=x;}
	fa[x]=z;
	fa[y]=x;
	fa[t[x][r]]=y;
	t[y][l]=t[x][r];
	t[x][r]=y;
	pushup(y);pushup(x);
}
inline void splay(int &k,int x)
{
	while (x!=k)
	{
		int y=fa[x],z=fa[y];
		if (y!=k)
		{
			if ((t[y][0]==x)^(t[z][0]==y)) rotate(k,x);
			else rotate(k,y);
		}
		rotate(k,x);
	}
}
inline int find(int k,int rank)
{
	if (tag[k]||rev[k]) pushdown(k);
	int l=t[k][0],r=t[k][1];
	if (size[l]+1==rank) return k;
	else if (size[l]>=rank) return find(l,rank);
	else return find(r,rank-size[l]-1);
}
inline void add(int l,int r,int val)
{
	int x=find(rt,l),y=find(rt,r+2);
	splay(rt,x);
	splay(t[x][1],y);
	int z=t[y][0];
	tag[z]+=val;mx[z]+=val;a[z]+=val;
}
inline void reverse(int l,int r)
{
	int x=find(rt,l),y=find(rt,r+2);
	splay(rt,x);splay(t[x][1],y);
	rev[t[y][0]]^=1;
}
inline void query(int l,int r)
{
	int x=find(rt,l),y=find(rt,r+2);
	splay(rt,x);splay(t[x][1],y);
	printf("%d\n",mx[t[y][0]]);
}
inline void build(int l,int r,int last)
{
	if (l>r) return;
	if (l==r)
	{
		fa[l]=last;size[l]=1;
		if (l>1;
	build(l,mid-1,mid);build(mid+1,r,mid);
	fa[mid]=last;pushup(mid);
	if (mid>1;
	F(i,1,m)
	{
		int flag=read(),l=read(),r=read(),val;
		if (flag==1){val=read();add(l,r,val);}
		else if (flag==2) reverse(l,r);
		else query(l,r);
	}
	return 0;
}