[NOI 2005] 维修数列: Splay

维护一个数列, 支持6种操作: 区间插入, 区间删除, 区间赋值, 区间翻转, 区间求和, 求和最大的连续子列. (插入数字的总数不超过4*10^6, 任何时刻数列中最多含5*10^5个数, 任何一个数字均在[-1000, 1000]内, 操作数不超过20000) 这是一道经典的Splay模板题.

树上维护信息的方法

线段树的结点的信息由子区间合并而来, 平衡树的结点上不仅有子树信息, 还有它自己的信息.

信息的维护分为两类, 自底向上和自顶向下. 举例. 自底向上: size, sum. 自顶向下: 各种标记, 如add, cover, reverse.

自底向上的更新通常发生在修改后的回溯过程中, 旋转之后 (带旋转的平衡树).

自顶向下的更新通常发生在访问之前. 需要保证访问之前, 结点的信息是最新的. 平衡树可以安全地进行旋转. 线段树上有时标记可以不下传, 只需计算时考虑它们的影响. 平衡树通常不行, 因为涉及形态的改变.

标记需要满足三个性质: 1. 可以快速计算出对本结点的影响. 2. 可以相互合并. 3. 如果有多种标记, 它们能相容.

本题需要维护v, size, sum, max_sum, max_pre, max_suf. 需要打赋值标记和翻转标记. 第一次打翻转标记的时候很惊奇, 没想到翻转区间还可以用这种递归的方式.

赋值标记: 影响到v, sum, max_sum, max_pre, max_suf.

翻转标记: 影响到max_pre, max_suf, 还得交换左右子树.

它们之间没有什么特殊的影响. 需要注意, 有时打翻转标记, 在下传的时候才swap, 这里不行, 因为涉及到max_pre和max_suf要为祖先所用.

另外, 本题内存限制较紧, 需要delete, 或者手写带释放的内存池.

使用前置声明就能在前面定义nil了. 一种避免忘记init的方法: 写在struct的构造函数里, 定义一个全局变量......

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;

const int null = -1001, inf = 1e8 + 1;

struct Node;
Node* nil;

struct Node {
	Node* ch[2], * fa;
	int v, sz, sum, ms, pre, suf, c;
	bool rev;

	Node(): fa(0), v(null), sz(0), sum(0), ms(-inf), pre(0), suf(0), c(null), rev(false)
	{
		ch[0] = ch[1] = nil;
	}

	Node(int v): fa(0), v(v), sz(1), sum(v), ms(v), c(null), rev(false)
	{
		ch[0] = ch[1] = nil;
		pre = suf = max(v, 0);
	}
	
	int type()
	{
		return this == fa->ch[1];
	}
	
	void setc(int t, Node* x)
	{
		(ch[t] = x)->fa = this;
	}
	
	void up()
	{
		Node* lc = ch[0], * rc = ch[1];
		sum = lc->sum + rc->sum + v;
		ms = max(max(lc->ms, rc->ms), lc->suf + v + rc->pre);
		pre = max(lc->pre, lc->sum + v + rc->pre);
		suf = max(rc->suf, rc->sum + v + lc->suf);
		sz = lc->sz + rc->sz + 1;
	}
	
	void reverse()
	{
		rev = !rev;
		swap(ch[0], ch[1]);
		swap(pre, suf);
	}

	void cover(int x)
	{
		if (this == nil) return;
		v = c = x;
		sum = x * sz;
		ms = x > 0 ? sum : x;
		pre = suf = max(sum, 0);
	}
	
	void down()
	{
		Node* &lc = ch[0], * &rc = ch[1];
		if (rev) {
			lc->reverse();
			rc->reverse();
			rev = false;
		}
		if (c != null) {
			lc->cover(c);
			rc->cover(c);
			c = null;
		}
	}
} * root;

void rot(Node* x, int t)
{
	Node* p = x->fa, * y = x->ch[t];
	if (p) p->setc(x->type(), y);
	else y->fa = 0, root = y;
	x->setc(t, y->ch[t^1]);
	y->setc(t^1, x);
	x->up();
	y->up();
}

void splay(Node* x, Node* top)
{
	Node* y, * z;
	int t1, t2;

	for (y = x->fa; y != top; y = x->fa) {
		t1 = x->type();
		z = y->fa;
		if (z != top) {
			t2 = y->type();
			if (t1 == t2)
				rot(z, t2), rot(y, t1);
			else
				rot(y, t1), rot(z, t2);
		} else
			rot(y, t1);
	}
}

void access(Node* x, int k, Node* r=0)
{
	while (true) {
		x->down();
		if (x->ch[0]->sz + 1 == k)
			break;
		if (x->ch[0]->sz >= k)
			x = x->ch[0];
		else {
			k -= x->ch[0]->sz + 1;
			x = x->ch[1];
		}
	}
	splay(x, r);
}

inline Node* split(int pos, int n)
{
	access(root, pos);
	access(root->ch[1], n+1, root);
	return root->ch[1]->ch[0];
}

inline void update()
{
	root->ch[1]->up();
	root->up();
}

inline void insert(int pos, Node* x)
{
	split(pos+1, 0);
	root->ch[1]->setc(0, x);
	update();
}

void release(Node* T)
{
	if (T == nil) return;
	release(T->ch[0]);
	release(T->ch[1]);
	delete T;
}

inline void erase(int pos, int n)
{
	split(pos, n);
	release(root->ch[1]->ch[0]);
	root->ch[1]->setc(0, nil);
	update();
}

inline void cover(int pos, int n, int v)
{
	split(pos, n)->cover(v);
	update();
}

inline void reverse(int pos, int n)
{
	split(pos, n)->reverse();
	update();
}

inline int get_sum(int pos, int n)
{
	return split(pos, n)->sum;
}

inline int max_sum()
{
	return root->ms;
}

Node* build(int* l, int* r)
{
	if (l > r) return nil;
	int* m = l + (r-l)/2;
	Node* T = new Node(*m);
	T->setc(0, build(l, m-1));
	T->setc(1, build(m+1, r));
	T->up();
	return T;
}

struct Init {
	Init()
	{
		nil = new Node;
	}
} I;

int main()
{
	int n, m;
	static int A[int(4e6)];
	char s[10];
	
	scanf("%d%d", &n, &m);
	For (i, 1, n)
		scanf("%d", &A[i]);
	A[0] = A[n+1] = null;

	root = build(A, A+n+1);
	
	while (m--) {
		int pos, tot, c;
		scanf("%s", s);
		
		if (s[2] == 'X') { // max_sum
			printf("%d\n", max_sum());
			continue;
		}
		
		scanf("%d%d", &pos, &tot);
		
		switch (s[0]) {
		case 'I': // insert
			Rep (i, 0, tot)
				scanf("%d", &A[i]);
			insert(pos, build(A, A+tot-1));
			break;
		case 'D': // delete
			erase(pos, tot);
			break;
		case 'R': // reverse
			reverse(pos, tot);
			break;
		case 'G': // get-sum
			printf("%d\n", get_sum(pos, tot));
			break;
		default: // make-same
			scanf("%d", &c);
			cover(pos, tot, c);
		}
	}

	return 0;
}