POJ

博主的 BiBi 时间

因为这题思路不是很好讲，所以讲解就是依据代码而谈，分析一下什么时候用什么函数。

( ext{Solution})

• 这道题的 ( ext{Splay}) 是区间平衡树而不是权值平衡树。其实这两种平衡树的区别就在于区间平衡树是维护整棵树的中序遍历（注意这里是输出键值）是数列进行许多次操作的值的样子，而权值平衡树的中序遍历是数列的值从小到大（当然也可以从大到小）排序。

• ( ext{Splay}) 的区间提取操作：将 (l-1) 提到根，再将 (r+1) 变成根的儿子（注意 (r+1) 肯定在 (l-1) 的右侧，所以提上去实际上是 (l-1)（即现在根）的右儿子）。显然由于 ([l,r]) 在两个点中间，现在就是 (r+1) 的左子树。

• 关于 ( ext{rotate()})：基础操作应该都懂，我只讲为什么 ( ext{pushDown()}) 以及 ( ext{pushUp()})。这里的 ( ext{pushDown()}) 是没有祖父的，因为祖父只是改变了一个儿子，无需下放。而 (fa) 和 (x) 改变了位置，必须下放。

• 哨兵节点：其实就是为了防止 (l=1,r=n) 的情况越界加的点，在实际统计时不会算到，所以不赋初值也无所谓。

• 题目要求操作不需要 ( ext{pushDown(}root))：当把 (l) 提到根时，已经将标记下放（可以考虑最后一次交换，即之前根与 (l) 的交换，具体就是 ( ext{rotate()}) 的 ( ext{pushDown(}fa), ext{pushDown(}x))），此时的 (root) 没有标记。

( ext{Code})

#include <cstdio>

#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)

template <class T> inline T read(const T sample) {
    T x=0; int f=1; char s;
    while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
    while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
    return x*f;
}
template <class T> inline void write(const T x) {
    if(x<0) return (void) (putchar('-'),write(-x));
    if(x>9) write(x/10);
    putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}

const int maxn=8e6+10;

int n;

struct Splay {
	int sz,rt,la[maxn],siz[maxn],key[maxn],son[maxn][2],f[maxn],data[maxn],tag[maxn],ans[maxn];
	
	bool dir(int x) {return son[f[x]][1]==x;}
	
	void clear(int x) {la[x]=siz[x]=key[x]=son[x][0]=son[x][1]=f[x]=tag[x]=ans[x]=0;}
	
	void add(int x,int fa,bool dir) {
		if(x) f[x]=fa;
		if(fa) son[fa][dir]=x; 
	}
	
	void pushUp(int o) {
		if(!o) return;
		siz[o]=siz[son[o][0]]+siz[son[o][1]]+1;
		ans[o]=key[o];
		if(son[o][0]) ans[o]=Min(ans[o],ans[son[o][0]]);
		if(son[o][1]) ans[o]=Min(ans[o],ans[son[o][1]]);
	}
	
	void pushDown(int o) {
		if(!o) return;
		if(la[o]) {
			if(son[o][0]) la[son[o][0]]+=la[o],key[son[o][0]]+=la[o],ans[son[o][0]]+=la[o];
			if(son[o][1]) la[son[o][1]]+=la[o],key[son[o][1]]+=la[o],ans[son[o][1]]+=la[o];
			la[o]=0; 
		}
		if(tag[o]) {
			if(son[o][0]) tag[son[o][0]]^=1;
			if(son[o][1]) tag[son[o][1]]^=1;
			Swap(son[o][0],son[o][1]);
			tag[o]=0;
		}
	}
	
	void rotate(int x) {
		int fa=f[x],ffa=f[fa],dx=dir(x),df=dir(fa);
		pushDown(fa),pushDown(x);
		add(son[x][dx^1],fa,dx);
		add(fa,x,dx^1);
		add(x,ffa,df);
		pushUp(fa),pushUp(x);
	}
	
	void splay(int x,int goal) {//将点 x 提到 goal 的儿子
		for(int fa;(fa=f[x])^goal;rotate(x))
			if(f[fa]^goal) rotate(dir(fa)==dir(x)?fa:x);
		if(!goal) rt=x;
	}
	
	int kth(int x) {
		int now=rt;
		while(1) {
			pushDown(now);
			if(siz[son[now][0]]>=x) now=son[now][0];
			else {
				x-=siz[son[now][0]]+1;
				if(!x) return now;
				now=son[now][1];
			}
		}
	}
	
	void plus(int x,int y,int k) {
		x=kth(x-1),y=kth(y+1);
		splay(x,0); splay(y,x);
		//pushDown(rt);
		la[son[y][0]]+=k; key[son[y][0]]+=k; ans[son[y][0]]+=k;
		pushUp(y),pushUp(rt); 
	}
	
	void newnode(int x,int fa,int val) {
		la[x]=tag[x]=son[x][0]=son[x][1]=0;
		siz[x]=1; key[x]=ans[x]=val; f[x]=fa;
	}
	
	int build(int fa,int l,int r) {
		if(l>r) return 0;
		int mid=l+r>>1,now=++sz;
		newnode(now,fa,data[mid]);
		son[now][0]=build(now,l,mid-1);
		son[now][1]=build(now,mid+1,r);
		pushUp(now);
		return now;
	}
	
	void Reverse(int x,int y) {
		x=kth(x-1),y=kth(y+1);
		splay(x,0),splay(y,x);
		//pushDown(rt);
		tag[son[y][0]]^=1;
		pushUp(y),pushUp(rt);
	}
	
	void Revolve(int x,int y,int t) {
		t%=(y-x+1);
		if(!t) return;
		int l=kth(y-t),r=kth(y+1);//将 [y-t+1,y] 提到 [x,y-t] 的前面就相当于旋转
		splay(l,0),splay(r,l);
		//pushDown(rt);
		int tmp=son[r][0]; son[r][0]=0;
		pushUp(r),pushUp(rt);
		l=kth(x-1),r=kth(x);
		splay(l,0),splay(r,l);
		//pushDown(rt);
		son[r][0]=tmp; f[tmp]=r;
		pushUp(r),pushUp(rt);
	}
	
	void insert(int x,int k) {
		int l=kth(x),r=kth(x+1);
		splay(l,0),splay(r,l);
		//pushDown(rt);
		son[r][0]=++sz; newnode(sz,r,k);
		pushUp(r),pushUp(rt);
	}
	
	void del(int x) {
		int l=kth(x-1),r=kth(x+1);
		splay(l,0),splay(r,l);
		//pushDown(rt);
		clear(son[r][0]); son[r][0]=0;
		pushUp(r),pushUp(rt);
	}
	
	int query(int x,int y) {
		x=kth(x-1),y=kth(y+1);
		splay(x,0),splay(y,x);
		//pushDown(rt);
		//pushUp(y),pushUp(rt);
		return ans[son[y][0]];//这里没有更改，显然不需要 pushUp() 了
	}
} T;

int main() {
	char ch[10]; int x,y,z;
	n=read(9);
	rep(i,2,n+1) T.data[i]=read(9);
	T.rt=T.build(0,1,n+2);
	for(int t=read(9);t;--t) {
		scanf("%s",ch); x=read(9);
		if(ch[0]=='A') y=read(9),z=read(9),T.plus(x+1,y+1,z);
		if(ch[0]=='R'&&ch[3]=='E') y=read(9),T.Reverse(x+1,y+1);
		if(ch[0]=='R'&&ch[3]=='O') y=read(9),z=read(9),T.Revolve(x+1,y+1,z);
		if(ch[0]=='I') y=read(9),T.insert(x+1,y);
		if(ch[0]=='D') T.del(x+1);
		if(ch[0]=='M') y=read(9),print(T.query(x+1,y+1),'
');
	}
	return 0;
}