[题解] poj 3580 SuperMemo(Splay)

- 传送门 -

#SuperMemo

Description

Your friend, Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first, the host tells the participant a sequence of numbers, {A₁, A₂, ... A_n}. Then the host performs a series of operations and queries on the sequence which consists:

ADD x y D: Add D to each number in sub-sequence {A_x ... A_y}. For example, performing "ADD 2 4 1" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5, 5}
REVERSE x y: reverse the sub-sequence {A_x ... A_y}. For example, performing "REVERSE 2 4" on {1, 2, 3, 4, 5} results in {1, 4, 3, 2, 5}
REVOLVE x y T: rotate sub-sequence {A_x ... A_y} T times. For example, performing "REVOLVE 2 4 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 2, 5}
INSERT x P: insert P after A_x. For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}
DELETE x: delete A_x. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}
MIN x y: query the participant what is the minimum number in sub-sequence {A_x ... A_y}. For example, the correct answer to "MIN 2 4" on {1, 2, 3, 4, 5} is 2

To make the show more interesting, the participant is granted a chance to turn to someone else that means when Jackson feels difficult in answering a query he may call you for help. You task is to watch the TV show and write a program giving the correct answer to each query in order to assist Jackson whenever he calls.

Input

The first line contains _n _(_n _≤ 100000).

The following n lines describe the sequence.

Then follows M (_M _≤ 100000), the numbers of operations and queries.

The following M lines describe the operations and queries.

Output

For each "MIN" query, output the correct answer.

Sample Input

5
1
2
3
4
5
2
ADD 2 4 1
MIN 4 5

Sample Output

[[Submit](http://poj.org/submit?problem_id=3580)] [[Status](http://poj.org/problemstatus?problem_id=3580)] [[Discuss](http://poj.org/bbs?problem_id=3580)]

- 题意 -

　你有个叫Jackson的基友.
　请你帮他维护一个数列.
　操作如下:
　1. ADD x y D: 区间 [x, y] 内每个数加D
　2. REVERSE x y: 区间 [x, y] 翻转
　3. REVOLVE x y T: 区间 [x, y] 的数字在区间内部向右移 T 位, 也就是后 T 位移到区间的前面来.
　4. INSERT x P: 第 x 位后插入 P.
　5. DELETE x: 删除第 x 位.
　6. MIN x y: 求区间 [x, y] 中最小值.
　~~不我没有这么烦人的基友~~
　

- 思路 -

　区间加和翻转和 最小值 就维护标记好了, 注意标记的下传与数据的更改.
　区间位移也就是把区间的的后 T 位切下来插到前面.
　插入和删除就日常前一位旋到 rt , 后一位旋到 rt 的右儿子啦.
　日常设虚点.
　~~老生常谈啦老生常谈~~

　细节见代码.

　PS:
　关于记录 splay 经过路径的问题, 我看的 AC 代码是没有记录并下传标记的, 于是我去问同机房Dalao:
　愚蠢的我: 为什么他不用把标记下传呢???
　充满智慧的 Dalao: 有的情况下这个标记是不影响的.
　愚蠢的我: 于是???
　充满智慧的 Dalao: 但是这个情况太复杂了我懒得分析.
　愚蠢的我: 喵喵喵???
　~~充满智慧的~~ Dalao: 所以管他的反正传一次标记卡不死你.
　愚蠢的我: ...
　~~充满智慧的~~ Dalao: 反正我是每次都传了.
　

- 代码 -

#include<cstdio>
#include<algorithm>
#include<cstring>
#define cl c[c[rt][1]][0]
#define ll c[x][0]
#define rr c[x][1]
using namespace std;

const int N = 2e5 + 5;
const int inf = 0x7fffffff;

int c[N][2]; //儿子
int f[N];  //爸爸
int s[N]; //size
int v[N]; //数值
int a[N]; //初始数列
int ad[N]; //增加标记
int re[N]; //翻转标记
int mi[N]; //最小值标记
int tmp[N]; //splay经过的路径
int n, m, tot, rt;

void read(int &x) {
	x = 0; int f = 1; char ch = getchar();
	while (ch > '9' || ch < '0') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x*10 + ch - '0'; ch = getchar(); }
	x *= f;
}

void Pd(int x) {
	if (x) {
		if (re[x]) {
			if (ll) re[ll] ^= 1; swap(c[ll][0], c[ll][1]);
			if (rr) re[rr] ^= 1; swap(c[rr][0], c[rr][1]);
			re[x] = 0;
		}
		if(ad[x]) {
			if (ll) ad[ll] += ad[x], v[ll] += ad[x], mi[ll] += ad[x];
			if (rr) ad[rr] += ad[x], v[rr] += ad[x], mi[rr] += ad[x];
			ad[x] = 0;
		}
	}//标记转移的同时就对节点造成了影响
}


void Ud(int x) {
	if (x) {
		mi[x] = v[x];
		if (ll) mi[x] = min(mi[ll], mi[x]); 
		if (rr) mi[x] = min(mi[rr], mi[x]);
		s[x] = s[ll] + s[rr] + 1;
	}
}

void rotate(int x, int &rot) {
	int y = f[x], z = f[y];
	int a = c[y][1] == x, b = a^1;
	if (y == rot) rot = x;
	else c[z][c[z][1] == y] = x;
	f[x] = z, f[y] = x, f[c[x][b]] = y;
	c[y][a] = c[x][b], c[x][b] = y;
	Ud(y), Ud(x);
}  

void Splay(int x, int &rot) {
	int mp = 1, k = x;
	tmp[mp] = k;
	while (f[k]) {
		k = f[k];
		tmp[++mp] = k;
	} 
	for (int i = mp; i >= 1; -- i) Pd(tmp[i]);
	//遍历一遍splay的路径,然后下传标记
	while (x != rot) {
		int y = f[x], z = f[y];
		if (y ^ rot) {
			if (c[y][1] == x ^ c[z][1] == y) rotate(x, rot);
			else rotate(y, rot);
		}
		rotate(x, rot);
	}
}

int Gp(int x, int k) {
    Pd(x); //注意标记的下传
	if (s[ll] + 1 == k) return x;
	if (s[ll] >= k) return Gp(ll, k);
	return Gp(rr, k - s[ll] - 1);
}

void Rr(int h, int b) {
	int x = Gp(rt, h), y = Gp(rt, b);
	Splay(x, rt), Splay(y, rr);
}

void Bd(int &t, int g, int l, int r) {
	if (l > r) return;
	t = ++ tot;
	if (l == r) {
		f[t] = g;
		s[t] = 1;
		v[t] = mi[t] = a[l]; //注意叶子节点min标记的初始化
	}
	else {
		int mid = l + r >> 1;
		v[t] = a[mid];
		f[t] = g;
		Bd(c[t][0], t, l, mid - 1),
		Bd(c[t][1], t, mid + 1, r);
		Ud(t);
	}
}

void Dl(int g) {
	Rr(g,  g+2);
	cl = 0;
}

void Gm(int b, int h) {
	Rr(b, h+2);
	printf("%d
", mi[cl]);
}

void Is(int g, int val) {
	Rr(g+1, g+2);
	cl = ++ tot;
	s[tot] = 1;
	mi[tot] = v[tot] = val;
	f[tot] = c[rt][1];
}

void Ad(int b, int h, int e) {
	Rr(b, h+2);	
	ad[cl] += e;
	v[cl] += e;
	mi[cl] += e;
}

void Rs(int b, int h) {
	Rr(b, h+2);	
	re[cl] ^= 1;
	swap(c[cl][0], c[cl][1]);
}

void Rt(int b, int h, int t) {
    t %= h - b + 1; //t 可能大于区间大小
    if (!t) return;
	Rr(h - t + 1, h + 2);
	int k = cl;
	cl = 0;
	Ud(c[rt][1]), Ud(rt);
	Rr(b, b+1);
	cl = k;
	f[k] = c[rt][1];
}

int main() {
	read(n);
	a[1] = a[n+2] = inf; //虚点,赋为 inf 确保对最小值标记无影响
	for (int i = 1; i <= n; ++ i) read(a[i+1]);
	Bd(rt, 0, 1, n+2);
    read(m);
	char st[10];
	int b, h, e;
	while (m --) {
		scanf("%s", st);
		if (st[0] == 'D') read(e), Dl(e);
		else if (st[0] == 'M') read(b), read(h), Gm(b, h);
		else if (st[0] == 'I') read(b), read(h), Is(b, h);
		else if (st[0] == 'A') read(b), read(h), read(e), Ad(b, h, e);
		else if (st[3] == 'E') read(b), read(h), Rs(b, h);
		else read(b), read(h), read(e), Rt(b, h, e);
		if (st[0] != 'M') Ud(c[rt][1]), Ud(rt);
	}
	return 0;
}