xpycc's Blog

都说 Splay 不仅仅是平衡树那么简单，由于它可以任意旋转，它还可以高效完成一些在区间上的操作，于是就做了几道 Splay 的题目。虽然不是很难，但很巧妙，也确实很烦，所以就取了 "Boring Sequence Manipulation" 这个标题，呵呵~ 下面进入正题。

其实 Splay 高效做区间操作的原理和线段树几乎一样，都是标记延迟，都是从根到叶，在维护的时候，也都是从叶到根的维护。只是 Splay 可以改变根和叶的关系，而线段树的根叶关系则不能改变。因而Splay 可以实现任意插入和删除结点，更为轻松地实现旋转(rotate)、翻转(reverse) 等操作。然而，这不是没有代价的，因为每次做 splay/rotate 操作时都会要求立即还原被延迟的标记，使被旋转结点能够正确地被维护，所以这样会有更大的常数。而且 Splay 的码量也较线段树大。

然而实际做题的时候，问题最大的还是标记延迟的实现，这也是写线段树的关键点。鉴于以往线段树的实践，与线段树一样，我的做法是，父结点的标记都是给儿子结点做的。也就是说，父结点的标记表示的确切意义是，父结点的信息已维护，子结点的信息未维护。这就很好地对应了 rotate 的意图，push_down 为的就是使子结点的信息得到更正，而不是父结点自己的信息得到更正。相应地，从 splay/rotate 的实现中可以看出，update 总是假定父结点的标记已传给子结点，即假定 update 之前一定做过 push_down 。于是两者结合，就可以保证正确性了。

更详细地，所有结点的信息有三类，标记信息、固有信息、子结点相关信息。其中，第一个和第三个是和线段树一致的，第三个由于经常和要求的答案有直接关系，所以也被称为答案信息。由于 splay 的结点，其本身是序列中的一个元素，所以，较线段树来说，又多了一个固有信息，即与子结点无关的信息。push_down 的作用就是维护子结点固有信息和答案信息，而 update 的作用就是根据固有信息和  新建立父子关系的子结点  的信息，维护其本身的答案信息。由于 splay 的结点，同一般的树一样，既可以看成是一个结点，也可以看成是一棵子树。因而，在从某个结点到树根路径的旋转过程中，可以到最后才 update 。因为在这条路径中，从父结点 push_down 保证了固有信息的正确性，虽然在 push_down 的过程中，答案信息是错误的，但是终将会在最后的 update 操作中得到更正。并且，对该结点的 push_down ，起到了一个传递信息的作用，保证了旋转过程中 其临时子结点 的信息的正确性，这点保证了路径上其他结点的 update 操作是正确的。又由于该结点的答案信息只与固有信息和 最后建立父子关系 的子结点的答案信息有关，所以可以省去中间过程中的 update 操作。再结合 push_down 保证了固有信息的正确性，而且 update 在 push_down 之后，满足 update 的假设，所以这样做是正确的，固有信息和答案信息的正确性都得到了保证。

最后就是 mark_xxx 函数，其作用是对于给定标记，维护某个结点的固有信息和答案信息，并做上标记。事实上 push_down 也是用它来实现的，在标记信息有多个的时候 push_down 实现对子结点做何种标记，即调用哪个 mark_xxx 函数。

另外，每次做完标记，或者单独更新（对于那些只更新单个结点的题目来说）的时候，最好把其父结点转到根的位置，保证整棵树的正确性（对于那些只更新单个结点的题目，还可以提高效率）。事实上，平常的带 _size 域实现的 Splay 平衡树的删除结点操作就是这样来完成的。

那么，了解原理之后，对于这些函数做出设定，其他的基本上就可以交给模板来完成了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXMEM 100010

template <class T>
struct Splay {
	struct Node {
		Node *_fa, *_ch[2];
		T _val;
		Node *_min_node;
		int _size;
		bool _rev;

		Node* get_end(int c) {			// 0 表示左端 1 表示右端
			Node* x = this;
			while (x->_ch[c]) {
				x->push_down();			// notice!
				x = x->_ch[c];
			}
			return x;
		}

		Node* get_near(int c) {
			if (_ch[c])
				return _ch[c]->get_end(1 - c);
			Node* x = this;
			while (x->_fa && x->_fa->_ch[c] == x)
				x = x->_fa;
			return x->_fa;
		}

		Node* get_succ() { return get_near(1); }
		Node* get_prev() { return get_near(0); }

		int get_size() {		// 兼容 this == 0
			if (this) return _size;
			else return 0;
		}

		void mark_node() {
			if (this) {
				_rev = !_rev;
				swap(_ch[0], _ch[1]);
			}
		}

		void push_down() {				// 向下传标记
			if (_rev) {
				_ch[0]->mark_node();
				_ch[1]->mark_node();
				_rev = false;
			}
		}

		void update() {					// 向上更新，可以为空
			_size = 1 + _ch[0]->get_size() + _ch[1]->get_size();
			_min_node = this;
			if (_ch[0] && _ch[0]->_min_node->_val < _min_node->_val)
				_min_node = _ch[0]->_min_node;
			if (_ch[1] && _ch[1]->_min_node->_val < _min_node->_val)
				_min_node = _ch[1]->_min_node;
		}
	};

	Node *_root;
	static Node *const _fa_root, _nodes[MAXMEM];

	void rotate(Node* x, int c) {    // 旋转操作，0 表示左旋，1 表示右旋
		Node* y = x->_fa;
		y->push_down(); x->push_down(); // y 在 x 之上，故先 y 后 x
		y->_ch[1 - c] = x->_ch[c];
		if (x->_ch[c])
			x->_ch[c]->_fa = y;
		x->_fa = y->_fa;
		if (y->_fa != _fa_root) {
			if (y->_fa->_ch[0] == y)
				y->_fa->_ch[0] = x;
			else
				y->_fa->_ch[1] = x;
		} else
			_root = x;
		x->_ch[c] = y;
		y->_fa = x;
		y->update();						// 维护 y
	}

	void splay(Node* x, Node *f) {    // 把结点 x 转到结点 f 下面
		x->push_down();
		while (x->_fa != f) {
			if (x->_fa->_fa == f) {
				if (x->_fa->_ch[0] == x)
					rotate(x, 1);
				else
					rotate(x, 0);
			} else {
				Node *y = x->_fa, *z = y->_fa;
				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);
				}
			}
		}
		x->update();
	}

	void build(int a, int b) {
		_root = make_tree(a, b);
		_root->_fa = _fa_root;
	}

	static Node* make_tree(int a, int b) {
		if (a > b)
			return 0;
		Node* root = _nodes + (a + b) / 2;
		root->_rev = false;
		root->_ch[0] = make_tree(a, root - _nodes - 1);
		if (root->_ch[0])
			root->_ch[0]->_fa = root;
		root->_ch[1] = make_tree(root - _nodes + 1, b);
		if (root->_ch[1])
			root->_ch[1]->_fa = root;
		root->update();
		return root;
	}
};

template <class T>
typename Splay<T>::Node *const Splay<T>::_fa_root = 0;
	
template <class T>
typename Splay<T>::Node Splay<T>::_nodes[MAXMEM];

Splay<pair<int, int> > tree;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int n;
	while (scanf("%d", &n) != EOF) {
		if (n == 0)
			break;
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &tree._nodes[i]._val.first);
			tree._nodes[i]._val.second = i;
		}
		tree._nodes[n + 1]._val = make_pair(0x7fffffff, 0x7fffffff);
		tree.build(0, n + 1);
		Splay<pair<int, int> >::Node * min_node = tree._nodes, *min_succ;
		for (int i = 1; i < n; ++i) {
			tree.splay(min_node, tree._fa_root);
			min_node = tree._root->_ch[1]->_min_node;
			tree.splay(min_node, tree._root);
			min_succ = min_node->get_succ();
			tree.splay(min_succ, tree._root);
			printf("%d ", i - 1 + min_succ->_ch[0]->get_size());
			min_succ->_ch[0]->mark_node();
		}
		printf("%d\n", n);
	}
    return 0;
}

简单的不带删除的翻转，push_down 、mark_node(以后叫 mark_rev) 和 update 写完了以后，就可以把任务交给模板了，不过要注意，由于翻转，所以 get_succ 的时候，要在路径上做维护，也就是不断地 push_down ，来得到真正的后继。不过其实这是在 get_end 里面完成的，因为已经旋转到根的下面，而且根已经被更新，所以可以直接调 get_succ ，因为它一定会调用 get_end 。所以更加严谨一些的话应该写 get_end ，不过由于意义上 get_succ 更明了，所以就写 get_succ 了。而且，对于有 _rev 这种信息的树来说，get_end 就必须要通过 push_down 来保证正确性。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 100000

const int MAXMEM = MAXN * 3 + 2;

int ans[MAXMEM], tot;

template <class T>
struct Splay {
	struct Node {
		Node *_fa, *_ch[2];
		T _val;
		int _size;
		bool _rev;

		Node* get_end(int c) {			// 0 表示左端 1 表示右端
			Node* x = this;
			x->push_down();				// notice!
			while (x->_ch[c]) {
				x = x->_ch[c];
				x->push_down();			// notice!
			}
			return x;
		}

		Node* get_near(int c) {
			if (_ch[c])
				return _ch[c]->get_end(1 - c);
			Node* x = this;
			while (x->_fa && x->_fa->_ch[c] == x)
				x = x->_fa;
			return x->_fa;
		}

		Node* get_succ() { return get_near(1); }
		Node* get_prev() { return get_near(0); }

		int get_size() {		// 兼容 this == 0
			if (this) return _size;
			else return 0;
		}

		void mark_node() {
			if (this) {
				_rev = !_rev;
				swap(_ch[0], _ch[1]);
			}
		}

		void push_down() {				// 向下传标记
			if (_rev) {
				_ch[0]->mark_node();
				_ch[1]->mark_node();
				_rev = false;
			}
		}

		void update() {					// 向上更新，可以为空
			_size = 1 + _ch[0]->get_size() + _ch[1]->get_size();
		}

		void travel() {
			push_down();
			if (_ch[0]) _ch[0]->travel();
			ans[tot++] = _val;
			if (_ch[1]) _ch[1]->travel();
		}
	};

	Node *_root;
	static Node *const _fa_root, _nodes[MAXMEM];

	void rotate(Node* x, int c) {    // 旋转操作，0 表示左旋，1 表示右旋
		Node* y = x->_fa;
		y->push_down(); x->push_down(); // y 在 x 之上，故先 y 后 x
		y->_ch[1 - c] = x->_ch[c];
		if (x->_ch[c])
			x->_ch[c]->_fa = y;
		x->_fa = y->_fa;
		if (y->_fa != _fa_root) {
			if (y->_fa->_ch[0] == y)
				y->_fa->_ch[0] = x;
			else
				y->_fa->_ch[1] = x;
		} else
			_root = x;
		x->_ch[c] = y;
		y->_fa = x;
		y->update();						// 维护 y
	}

	void splay(Node* x, Node *f) {    // 把结点 x 转到结点 f 下面
		x->push_down();
		while (x->_fa != f) {
			if (x->_fa->_fa == f) {
				if (x->_fa->_ch[0] == x)
					rotate(x, 1);
				else
					rotate(x, 0);
			} else {
				Node *y = x->_fa, *z = y->_fa;
				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);
				}
			}
		}
		x->update();
	}

	Node* find_kth(int k) {
		Node* x = _root;
		x->push_down();				// notice!
		while (k != x->_ch[0]->get_size() + 1) {
			if (k <= x->_ch[0]->get_size()) {
				x = x->_ch[0];
			} else {
				k -= x->_ch[0]->get_size() + 1;
				x = x->_ch[1];
			}
			x->push_down();			// notice!
		}
		return x;
	}

	void build(int a, int b) {
		_root = make_tree(a, b);
		_root->_fa = _fa_root;
	}

	static Node* make_tree(int a, int b) {
		if (a > b)
			return 0;
		Node* root = _nodes + (a + b) / 2;
		root->_rev = false;
		root->_ch[0] = make_tree(a, root - _nodes - 1);
		if (root->_ch[0])
			root->_ch[0]->_fa = root;
		root->_ch[1] = make_tree(root - _nodes + 1, b);
		if (root->_ch[1])
			root->_ch[1]->_fa = root;
		root->update();				// notice!
		return root;
	}

	void dispaly() {
		tot = 0;
		_root->travel();
	}
};

template <class T>
typename Splay<T>::Node *const Splay<T>::_fa_root = 0;
	
template <class T>
typename Splay<T>::Node Splay<T>::_nodes[MAXMEM];

Splay<int> tree;
char buf[100];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int n, m;
	while (scanf("%d%d", &n, &m) != EOF) {
		if (n < 0 && m < 0)
			break;
		for (int i = 1; i <= n + 1; ++i)
			tree._nodes[i]._val = i;
		tree.build(0, n + 1);
		for (int i = 0; i < m; ++i) {
			scanf("%s", buf);
			int a, b, c;
			if (buf[0] == 'C') {
				scanf("%d%d%d", &a, &b, &c);
				tree.splay(tree.find_kth(a), tree._fa_root);
				tree.splay(tree.find_kth(b + 2), tree._root);
				Splay<int>::Node* handle = tree._root->_ch[1]->_ch[0];
				tree._root->_ch[1]->_ch[0] = 0;
				tree.splay(tree._root->_ch[1], tree._fa_root);

				tree.splay(tree.find_kth(c + 1), tree._fa_root);
				tree.splay(tree._root->get_succ(), tree._root);
				tree._root->_ch[1]->_ch[0] = handle;
				handle->_fa = tree._root->_ch[1];		// notice;
				tree.splay(tree._root->_ch[1], tree._fa_root);
			} else {
				scanf("%d%d", &a, &b);
				tree.splay(tree.find_kth(a), tree._fa_root);
				tree.splay(tree.find_kth(b + 2), tree._root);
				tree._root->_ch[1]->_ch[0]->mark_node();
				tree.splay(tree._root->_ch[1], tree._fa_root);
			}
		}
		tree.dispaly();
		for (int i = 1; i <= n; ++i) {
			if (i != 1) putchar(' ');
			printf("%d", ans[i]);
		}
		putchar('\n');
	}
    return 0;
}

带删除和插入以及查询第 k 个结点的区间翻转，基本同上，find_kth 跟 get_end 一样，在 _rev 环境下需要 push_down 保证正确性。本机调试的时候忘记维护父指针了，结果爆栈。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 100000

const int MAXMEM = MAXN * 2 + 1;

int pick[MAXN + 1], tot;
pair<int, int> seg[MAXN * 2 + 1];
int stot;

template <class T>
struct Splay {
	struct Node {
		Node *_fa, *_ch[2];
		T _val;
		int _size;

		Node* get_end(int c) {			// 0 表示左端 1 表示右端
			Node* x = this;
			x->push_down();				// notice!
			while (x->_ch[c]) {
				x = x->_ch[c];
				x->push_down();			// notice!
			}
			return x;
		}

		Node* get_near(int c) {
			if (_ch[c])
				return _ch[c]->get_end(1 - c);
			Node* x = this;
			while (x->_fa && x->_fa->_ch[c] == x)
				x = x->_fa;
			return x->_fa;
		}

		Node* get_succ() { return get_near(1); }
		Node* get_prev() { return get_near(0); }

		int get_size() {		// 兼容 this == 0
			if (this) return _size;
			else return 0;
		}

		void push_down() {}				// 向下传标记

		void update() {					// 向上更新，可以为空
			_size = _val.second - _val.first + 1
				+ _ch[0]->get_size() + _ch[1]->get_size();
		}
	};

	Node *_root;
	static Node *const _fa_root, _nodes[MAXMEM];

	void rotate(Node* x, int c) {    // 旋转操作，0 表示左旋，1 表示右旋
		Node* y = x->_fa;
		y->push_down(); x->push_down(); // y 在 x 之上，故先 y 后 x
		y->_ch[1 - c] = x->_ch[c];
		if (x->_ch[c])
			x->_ch[c]->_fa = y;
		x->_fa = y->_fa;
		if (y->_fa != _fa_root) {
			if (y->_fa->_ch[0] == y)
				y->_fa->_ch[0] = x;
			else
				y->_fa->_ch[1] = x;
		} else
			_root = x;
		x->_ch[c] = y;
		y->_fa = x;
		y->update();						// 维护 y
	}

	void splay(Node* x, Node *f) {    // 把结点 x 转到结点 f 下面
		x->push_down();
		while (x->_fa != f) {
			if (x->_fa->_fa == f) {
				if (x->_fa->_ch[0] == x)
					rotate(x, 1);
				else
					rotate(x, 0);
			} else {
				Node *y = x->_fa, *z = y->_fa;
				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);
				}
			}
		}
		x->update();
	}

	Node* join(Node* r1, Node* r2) {
		if (r1 && r2) {
			Node *right_end = r1->get_end(1);
			splay(right_end, r1->_fa);
			right_end->_ch[1] = r2;
			r2->_fa = right_end;
			right_end->update();		// notice!
			return right_end;
		}
		if (r1) return r1;
		if (r2) return r2;
		return 0;
	}

	int find_kth_number(int k) {
		Node* x = _root;
		x->push_down();				// notice!
		while (
			!(x->_ch[0]->get_size() < k &&
			k <= x->_ch[0]->get_size() + x->_val.second - x->_val.first + 1)
		) {
			if (k <= x->_ch[0]->get_size()) {
				x = x->_ch[0];
			} else {
				k -= x->_ch[0]->get_size() + x->_val.second - x->_val.first + 1;
				x = x->_ch[1];
			}
			x->push_down();			// notice!
		}
		int res = x->_val.first - 1 + k - x->_ch[0]->get_size();
		splay(x, _fa_root);
		return res;
	}
	
	void delete_node(Node* nd) {
		Node* x = join(nd->_ch[0], nd->_ch[1]);
		if (nd->_fa == _fa_root) {
			_root = x;
		} else {
			if (nd->_fa->_ch[0] == nd)
				nd->_fa->_ch[0] = x;
			else
				nd->_fa->_ch[1] = x;
		}
		if (x)
			x->_fa = nd->_fa;
		if (nd->_fa)
			splay(nd->_fa, _fa_root);
	}

	void build(int a, int b) {
		_root = make_tree(a, b);
		_root->_fa = _fa_root;
	}

	static Node* make_tree(int a, int b) {
		if (a > b)
			return 0;
		Node* root = _nodes + (a + b) / 2;
		root->_val = seg[(a + b) / 2];
		root->_ch[0] = make_tree(a, root - _nodes - 1);
		if (root->_ch[0])
			root->_ch[0]->_fa = root;
		root->_ch[1] = make_tree(root - _nodes + 1, b);
		if (root->_ch[1])
			root->_ch[1]->_fa = root;
		root->update();				// notice!
		return root;
	}
};

template <class T>
typename Splay<T>::Node *const Splay<T>::_fa_root = 0;
	
template <class T>
typename Splay<T>::Node Splay<T>::_nodes[MAXMEM];

Splay<pair<int, int> > tree;
char buf[100];

int n, m;

struct Query {
	char _c;
	int _x;
} q[MAXN];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int test;
	scanf("%d", &test);
	for (int cas = 1; cas <= test; ++cas) {
		scanf("%d%d", &n, &m);

		tot = 0;
		for (int i = 0; i < m; ++i) {
			scanf("%s%d", buf, &q[i]._x);
			q[i]._c = buf[0];
			if (q[i]._c != 'R')
				pick[tot++] = q[i]._x;
		}

		sort(pick, pick + tot);
		tot = unique(pick, pick + tot) - pick;
		pick[tot] = n + 1;
		stot = 0;
		if (pick[0] != 1)
			seg[stot++] = make_pair(1, pick[0] - 1);
		for (int i = 0; i < tot; ++i) {
			seg[stot++] = make_pair(pick[i], pick[i]);
			if (pick[i] + 1 != pick[i + 1])
				seg[stot++] = make_pair(pick[i] + 1, pick[i + 1] - 1);
		}

		tree.build(0, stot - 1);
		printf("Case %d:\n", cas);
		for (int i = 0; i < m; ++i) {
			if (q[i]._c == 'T') {
				int pos = lower_bound(seg, seg + stot, make_pair(q[i]._x, q[i]._x)) - seg;
				Splay<pair<int, int> >::Node* nd = tree._nodes + pos;
				tree.delete_node(nd);
				nd->_fa = tree._fa_root;
				nd->_ch[0] = 0;	nd->_ch[1] = tree._root;
				if (tree._root)				// notice!
					tree._root->_fa = nd;
				tree._root = nd; nd->update();
			} else if (q[i]._c == 'Q') {
				int pos = lower_bound(seg, seg + stot, make_pair(q[i]._x, q[i]._x)) - seg;
				Splay<pair<int, int> >::Node* nd = tree._nodes + pos;
				tree.splay(nd, tree._fa_root);
				printf("%d\n", tree._root->_ch[0]->get_size() + 1);
			} else {	// 'R'
				printf("%d\n", tree.find_kth_number(q[i]._x));
			}
		}
	}
    return 0;
}

这题没有 push_down ，应该说更简单些吧。Splay 上的离线化操作，由于 Top 的特殊性，所以可以离散化后，根据内存的固定性，离线来做。如果 Top x 是说当前第 x 个人到前端，那么可以用动态新建结点，动态插入来实现。这题我刚开始忘记考虑删除之后，可能会得到空树了，结果 RE =          =... 之前都是 1Y 的，没想到在这题上被打破了。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXMEM 500002

int arr[MAXMEM];

template <class T>
struct Splay {
	struct Node {
		Node *_fa, *_ch[2];
		T _val, _clear_val, _sum, _max_rsum, _max_lsum, _max_sum;
		int _size;		// _size 可以不要，标记这里加
		bool _rev, _clr;

		int get_size() {		// 兼容 this == 0
			if (this) return _size;
			else return 0;
		}

		int get_sum() {
			if (this) return _sum;
			else return 0;
		}

		int get_max_lsum() {
			if (this) return _max_lsum;
			else return 0;
		}

		int get_max_rsum() {
			if (this) return _max_rsum;
			else return 0;
		}

		Node() {}
		Node(const T& x) { set_value(x); }

		void *operator new(size_t) {
			if (_stop != 0) return _st[--_stop];
			else return _nodes + _mtot++;
		}

		void operator delete(void* p, size_t) {
			_st[_stop++] = (Node*)p;
		}

		void recycle() {
			if (_ch[0]) _ch[0]->recycle();
			if (_ch[1]) _ch[1]->recycle();
			delete this;
		}

		void set_value(const T& x) {
			_val = x; _size = 1;
			_rev = _clr = false;
			_sum = _max_sum = x;
			_max_lsum = max(0, x);
			_max_rsum = max(0, x);
			_ch[0] = _ch[1] = 0;
			_fa = _fa_root;
		}

		void mark_rev() {
			if (this && !_clr) {
				_rev = !_rev;
				swap(_ch[0], _ch[1]);
				swap(_max_lsum, _max_rsum);
			}
		}

		void mark_clear(const T& v) {
			if (this) {
				_clr = true;
				_clear_val = _val = v;			// notice!
				_sum = v * _size;
				_max_lsum = max(0, v * _size);
				_max_rsum = max(0, v * _size);
				_max_sum = max(v, v * _size);
				_rev = false;
			}
		}

		void push_down() {				// 向下传标记
			if (_rev) {
				_ch[0]->mark_rev();
				_ch[1]->mark_rev();
				_rev = false;
			} else if(_clr) {
				_ch[0]->mark_clear(_clear_val);
				_ch[1]->mark_clear(_clear_val);
				_clr = false;
			}
		}

		void update_size() {
			_size = 1 + _ch[0]->get_size() + _ch[1]->get_size();
		}

		void update_sum() {
			_sum = _val + _ch[0]->get_sum() + _ch[1]->get_sum();
		}

		void update_max_sum() {
			_max_sum = _ch[0]->get_max_rsum() + _val + _ch[1]->get_max_lsum();
			if (_ch[0]) _max_sum = max(_max_sum, _ch[0]->_max_sum);
			if (_ch[1]) _max_sum = max(_max_sum, _ch[1]->_max_sum);
		}

		void update_max_lsum() {
			_max_lsum = max(_ch[0]->get_max_lsum(), _ch[0]->get_sum() + _val + _ch[1]->get_max_lsum());
		}

		void update_max_rsum() {
			_max_rsum = max(_ch[1]->get_max_rsum(), _ch[1]->get_sum() + _val + _ch[0]->get_max_rsum());
		}

		void update() {					// 向上更新
			update_size();
			update_sum();
			update_max_sum();
			update_max_lsum();
			update_max_rsum();
		}
	};

	Node *_root;
	static Node *const _fa_root, _nodes[MAXMEM], *_st[MAXMEM];
	static int _mtot, _stop;

	void rotate(Node* x, int c) {    // 旋转操作，0 表示左旋，1 表示右旋
		Node* y = x->_fa;
		y->push_down(); x->push_down(); // y 在 x 之上，故先 y 后 x
		y->_ch[1 - c] = x->_ch[c];
		if (x->_ch[c])
			x->_ch[c]->_fa = y;
		x->_fa = y->_fa;
		if (y->_fa != _fa_root) {
			if (y->_fa->_ch[0] == y)
				y->_fa->_ch[0] = x;
			else
				y->_fa->_ch[1] = x;
		} else
			_root = x;
		x->_ch[c] = y;
		y->_fa = x;
		y->update();						// 维护 y
	}

	void splay(Node* x, Node *f) {    // 把结点 x 转到结点 f 下面
		x->push_down();
		while (x->_fa != f) {
			if (x->_fa->_fa == f) {
				if (x->_fa->_ch[0] == x)
					rotate(x, 1);
				else
					rotate(x, 0);
			} else {
				Node *y = x->_fa, *z = y->_fa;
				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);
				}
			}
		}
		x->update();
	}

	Node* find_kth(int k) {
		Node* x = _root;
		x->push_down();				// notice!
		while (k != x->_ch[0]->get_size() + 1) {
			if (k <= x->_ch[0]->get_size()) {
				x = x->_ch[0];
			} else {
				k -= x->_ch[0]->get_size() + 1;
				x = x->_ch[1];
			}
			x->push_down();			// notice!
		}
		return x;
	}

	void build(int a, int b) {
		_root = make_tree(a, b);
		if (_root)
			_root->_fa = _fa_root;
	}

	static Node* make_tree(int a, int b) {
		if (a > b)
			return 0;
		int mid = (a + b) / 2;
		Node* root = new Node(arr[mid]);
		root->_ch[0] = make_tree(a, mid - 1);
		if (root->_ch[0])
			root->_ch[0]->_fa = root;
		root->_ch[1] = make_tree(mid + 1, b);
		if (root->_ch[1])
			root->_ch[1]->_fa = root;
		root->update();				// notice!
		return root;
	}

	void clear() {
		_root = 0;
	}

	static void mem_init() {
		_mtot = _stop = 0;
	}
};

template <class T>
typename Splay<T>::Node *const Splay<T>::_fa_root = 0;

template <class T>
typename Splay<T>::Node Splay<T>::_nodes[MAXMEM];

template <class T>
typename Splay<T>::Node* Splay<T>::_st[MAXMEM];

template <class T>
int Splay<T>::_stop = 0;

template <class T>
int Splay<T>::_mtot = 0;

int n, m;

Splay<int> tree;

char buf[100];

inline void pre_operation(int s, int e) {
	Splay<int>::Node *pa = tree.find_kth(s), *pb = tree.find_kth(e);
	tree.splay(pa, tree._fa_root);
	tree.splay(pb, tree._root);
}

inline void post_operation() {
	tree.splay(tree._root->_ch[1], tree._fa_root);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int test;
	scanf("%d", &test);
	for (int cas = 1; cas <= test; ++cas) {
		tree.mem_init();
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; ++i)
			scanf("%d", arr + i);
		tree.build(0, n + 1);
		for (int i = 0; i < m; ++i) {
			scanf("%s", buf);
			int k, t, v;
			switch (buf[0]) {
			case 'M':
				if (buf[2] == 'K') {	// MAKE-SAME
					scanf("%d%d%d", &k, &t, &v);
					pre_operation(k, k + t + 1);
					tree._root->_ch[1]->_ch[0]->mark_clear(v);
					post_operation();
				} else {				// MAX-SUM
					pre_operation(1, tree._root->get_size());
					printf("%d\n", tree._root->_ch[1]->_ch[0]->_max_sum);
				}
				break;
			case 'I': {					// INSERT
					scanf("%d%d", &k, &t);
					pre_operation(k + 1, k + 2);
					for (int i = 0; i < t; ++i)
						scanf("%d", arr + i);
					Splay<int>::Node* h = Splay<int>::make_tree(0, t - 1);
					tree._root->_ch[1]->_ch[0] = h;
					if (h) h->_fa = tree._root->_ch[1];
					post_operation();
				}
				break;
			case 'D': {					// DELETE
					scanf("%d%d", &k, &t);
					pre_operation(k, k + t + 1);
					Splay<int>::Node* h = tree._root->_ch[1]->_ch[0];
					tree._root->_ch[1]->_ch[0] = 0;
					if (h) h->recycle();
					post_operation();
				}
				break;
			case 'R': {					// REVERSE
					scanf("%d%d", &k, &t);
					pre_operation(k, k + t + 1);
					tree._root->_ch[1]->_ch[0]->mark_rev();
					post_operation();
				}
				break;
			case 'G': {					// GET-SUM
					scanf("%d%d", &k, &t);
					pre_operation(k, k + t + 1);
					printf("%d\n", tree._root->_ch[1]->_ch[0]->get_sum());
				}
				break;
			}
		}
	}
	return 0;
}

比较麻烦的题，两种标记，_clr 和 _rev 都有，然后还有插入删除，以及最最ws的 MAX-SUM 询问，最后加起来，结点内信息的个数就相当恐怖了。再加上是在十分疲劳的状态下写的，于是 RE 和 WA了 N 次之后，终于 AC 。首先，这题的数据里，有一个 GET-SUM 的 tot 是 0 ，会导致非法解引用，找出这个错误，花了大概 N/3 个 RE 。之后一直 WA ，最后发现，原来是 mark_clear 里面，_val 忘记更新了，囧~ 这个错误真是太水了。这题最麻烦的还是两个标记的处理，我的做法是延续线段树时代的做法，由于 _clr 的特殊性质，每次保证标记信息中 _clr 和 _rev 里面只有一个为 true ，然后就好处理了。还有就是在 DELETE 那个地方，我纠结了好久，终于决定的方式返还内存了。开始是想返还内存的，但是想到普通实现用 new 的时候就会  ，觉得得不偿失，最后没有采用。忽然想到一种 del 操作 new 操作 的实现，不过比较麻烦，那就以后实现吧。

最后有个小插曲，我发现，在 SPOJ 上 AC 的代码，在衡阳八中 OJ 上，居然 WA 了。一开始以为是数据错了，搞了半天发现，果然是数据问题，SPOJ 把数据合并了，开头有个 test ，而衡阳八中 OJ 是原始 NOI2005 数据，开头没有 test 。做到这里，我差点晕过去，果然状态不好的时候不应该碰这种繁琐题的 =           =...

ps. 今天还有个插曲，我居然想不通如何维护乘法和加法的标记延迟了，囧~ 这什么状态，最后经大神提醒，终于知道怎么搞了。唉，看来今天是比较悲剧的。。。