「NOI2005」维护数列

传送门

维护过程有点像线段树。

但我们知道线段树的节点并不是实际节点，而平衡树的节点是实际节点。

所以在向上合并信息时要加入根节点信息。

然后节点再删除后编号要回退（栈），不然会爆空间。

具体实现看代码就好了。

参考代码：

#include <algorithm>

#include <cstdlib>

#include <cstdio>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

template < class T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while ('0' > c || c > '9') f |= c == '-', c = getchar();

	while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

const int _ = 1e6 + 2;

int tot, tmp[_];

int n, q, rt, siz[_], pri[_], ch[2][_];

int val[_], mx[_], L[_], R[_], sum[_], rev[_], tag[_], flag[_];

inline int Newnode(int v) {

	int id = tmp[tot--];

	siz[id] = 1, pri[id] = rand();

	val[id] = mx[id] = sum[id] = v, L[id] = R[id] = max(0, v);

	ch[0][id] = ch[1][id] = rev[id] = flag[id] = 0;

	return id;

}

inline void pushup(int p) {

	siz[p] = siz[ch[0][p]] + siz[ch[1][p]] + 1;

	sum[p] = sum[ch[0][p]] + sum[ch[1][p]] + val[p];

	L[p] = max(0, max(L[ch[0][p]], sum[ch[0][p]] + val[p] + L[ch[1][p]]));

	R[p] = max(0, max(R[ch[1][p]], sum[ch[1][p]] + val[p] + R[ch[0][p]]));

	mx[p] = max(val[p], R[ch[0][p]] + val[p] + L[ch[1][p]]);

	if (ch[0][p]) mx[p] = max(mx[p], mx[ch[0][p]]);

	if (ch[1][p]) mx[p] = max(mx[p], mx[ch[1][p]]);

}

inline void Rev(int p) {

	rev[p] ^= 1, swap(L[p], R[p]), swap(ch[0][p], ch[1][p]);

}

inline void Tag(int p, int v) {

	flag[p] = 1, val[p] = tag[p] = v, sum[p] = siz[p] * v;

	L[p] = R[p] = max(0, sum[p]), mx[p] = max(val[p], sum[p]);

}

inline void pushdown(int p) {

	if (rev[p]) {

		if (ch[0][p]) Rev(ch[0][p]);

		if (ch[1][p]) Rev(ch[1][p]);

		rev[p] = 0;

	}

	if (flag[p]) {

		if (ch[0][p]) Tag(ch[0][p], tag[p]);

		if (ch[1][p]) Tag(ch[1][p], tag[p]);

		flag[p] = 0;

	}

}

inline int merge(int x, int y) {

	if (!x || !y) return x + y;

	if (pri[x] > pri[y])

		return pushdown(x), ch[1][x] = merge(ch[1][x], y), pushup(x), x;

	else

		return pushdown(y), ch[0][y] = merge(x, ch[0][y]), pushup(y), y;

}

inline void split(int p, int k, int& x, int& y) {

	if (p) pushdown(p);

	if (!p) { x = y = 0; return ; }

	if (siz[ch[0][p]] + 1 <= k)

		return x = p, split(ch[1][p], k - siz[ch[0][p]] - 1, ch[1][x], y), pushup(p);

	else

		return y = p, split(ch[0][p], k, x, ch[0][y]), pushup(p);

}

inline void erase(int p) {

	if (!p) return ;

	tmp[++tot] = p;

	if (ch[0][p]) erase(ch[0][p]);

	if (ch[1][p]) erase(ch[1][p]);

}

int main() {

	srand((unsigned long long) new char);

	read(n), read(q);

	for (rg int i = 1; i <= 500000; ++i) tmp[++tot] = i;

	for (rg int v, i = 1; i <= n; ++i) read(v), rt = merge(rt, Newnode(v));

	char s[15];

	for (int pos, x, v, a, b, c; q--; ) {

		scanf("%s", s);

		if (s[0] == 'I') {

			read(pos), read(x);

			split(rt, pos, a, b);

			while (x--) read(c), a = merge(a, Newnode(c));

			rt = merge(a, b);

		}

		if (s[0] == 'D') {

			read(pos), read(x);

			split(rt, pos - 1, a, b);

			split(b, x, b, c);

			erase(b);

			rt = merge(a, c);

		}

		if (s[0] == 'M' && s[2] == 'K') {

			read(pos), read(x), read(v);

			split(rt, pos - 1, a, b);

			split(b, x, b, c);

			Tag(b, v);

			rt = merge(a, merge(b, c));

		}

		if (s[0] == 'R') {

			read(pos), read(x);

			split(rt, pos - 1, a, b);

			split(b, x, b, c);

			Rev(b);

			rt = merge(a, merge(b, c));

		}

		if (s[0] == 'G') {

			read(pos), read(x);

			split(rt, pos - 1, a, b);

			split(b, x, b, c);

			printf("%d\n", sum[b]);

			rt = merge(a, merge(b, c));

		}

		if (s[0] == 'M' && s[2] == 'X')

			printf("%d\n", mx[rt]);

	}

	return 0;

}

巴特西

「NOI2005」维护数列

「NOI2005」维护数列

最新文章

热门文章