记录编号	560699	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]维护数列	最终得分	100
用户昵称	huaruoji	是否通过	通过
代码语言	C++	运行时间	3.245 s
提交时间	2021-05-07 14:42:22	内存使用	22.58 MiB

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;

using namespace std;
const int N = 5e5 + 5;
int n, m, input[N];

namespace treap {
	#define lc(x) ch[x][0]
	#define rc(x) ch[x][1]
	
	int ch[N][2], val[N], sum[N], rnd[N], sz[N], rt, tot;
	int rtag[N], ctag[N], cov[N]; // reverse tag, change tag
	int lx[N], rx[N], mx[N];
	void update(int x) {
		if(!x) return;
		sz[x] = sz[lc(x)] + sz[rc(x)] + 1;
		sum[x] = sum[lc(x)] + sum[rc(x)] + val[x];
		mx[x] = max(rx[lc(x)] + lx[rc(x)], 0) + val[x];
		if(lc(x)) mx[x] = max(mx[x], mx[lc(x)]);
		if(rc(x)) mx[x] = max(mx[x], mx[rc(x)]);
		lx[x] = max(max(lx[lc(x)], sum[lc(x)] + val[x] + lx[rc(x)]), 0);
		rx[x] = max(max(rx[rc(x)], sum[rc(x)] + val[x] + rx[lc(x)]), 0);
	}
	stack <int> mem;
	void memDel(int u) { // 内存回收 
		mem.push(u);
		if(lc(u)) memDel(lc(u));
		if(rc(u)) memDel(rc(u));
	}
	void newNode(int &t, int x, int pos = 0) {
		if(mem.empty()) pos = ++tot;
		else pos = mem.top(), mem.pop();
		
		val[pos] = sum[pos] = mx[pos] = x, sz[pos] = 1, rnd[pos] = rand();
		rtag[pos] = ctag[pos] = lc(pos) = rc(pos) = 0; 
		lx[pos] = rx[pos] = max(x, 0);
		t = pos;
	}
	inline void reverse(int x) {
		if(!x) return;
		swap(lx[x], rx[x]);
	}
	void change(int x, int c) {
		if(!x) return;
		val[x] = cov[x] = c;
		sum[x] = val[x] * sz[x];
		lx[x] = rx[x] = max(0, sum[x]);
		mx[x] = max(c, sum[x]);
	}
	void pushDown(int x) {
		if(!x) return;
		if(rtag[x]) {
			reverse(lc(x)), reverse(rc(x));
			if(lc(x)) rtag[lc(x)] ^= 1;
			if(rc(x)) rtag[rc(x)] ^= 1;
			swap(lc(x), rc(x));
			rtag[x] = 0;
		}
		if(ctag[x]) {
			change(lc(x), cov[x]), change(rc(x), cov[x]);
			if(lc(x)) ctag[lc(x)] = 1;
			if(rc(x)) ctag[rc(x)] = 1;
			ctag[x] = cov[x] = 0;
		}
	}
	int merge(int x, int y) {
		if(!x || !y) return x | y;
		if(rnd[x] < rnd[y]) {
			pushDown(x);
			rc(x) = merge(rc(x), y);
			update(x);
			return x;
		} else {
			pushDown(y);
			lc(y) = merge(x, lc(y));
			update(y);
			return y;
		}
	}
	void split(int p, int v, int &x, int &y) {	
		if(!p) {
			x = y = 0;
			return;
		}
		pushDown(p);
		if(sz[lc(p)] < v) {
			x = p;
			split(rc(x), v - sz[lc(x)] - 1, rc(x), y);
		} else {
			y = p;
			split(lc(y), v, x, lc(y));
		}
		update(p);
	}
	int add(int l, int r) {
		int pos = 0;
		if(l > r) return 0;
		if(l == r) newNode(pos, input[l]);
		else {
			int mid = (l + r) >> 1;
			newNode(pos, input[mid]);
			lc(pos) = add(l, mid - 1); 
			rc(pos) = add(mid + 1, r);
			update(pos);
		}
		return pos;
	}
}
using namespace treap;

int main() {
	freopen("seq2005.in", "r", stdin);
	freopen("seq2005.out", "w", stdout);
	
	ios::sync_with_stdio(false); cin.tie(0);
	srand(time(0));
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> input[i];
	rt = add(1, n);
	string op; int pos, t;
	for(int i = 1, x, a, b, c; i <= m; i++) {
		cin >> op;
		if(op[2] != 'X') cin >> pos >> t;
		if(op[2] == 'S') {
			split(rt, pos, a, b);
			for(int i = 1; i <= t; i++) cin >> input[i];
			rt = merge(merge(a, add(1, t)), b);
		} else if(op[2] == 'L') {
			split(rt, pos - 1, a, b), split(b, t, b, c);
			memDel(b);
			rt = merge(a, c);
		} else if(op[2] == 'K') {
			cin >> x;
			split(rt, pos - 1, a, b), split(b, t, b, c);
			change(b, x), ctag[b] = 1;
			rt = merge(a, merge(b, c));
		} else if(op[2] == 'V') {
			split(rt, pos - 1, a, b), split(b, t, b, c);
			swap(lx[b], rx[b]), rtag[b] ^= 1;
			rt = merge(a, merge(b, c));
		} else if(op[2] == 'T') {
			split(rt, pos - 1, a, b), split(b, t, b, c);
			cout << sum[b] << endl;
			rt = merge(a, merge(b, c));
		}
		else cout << mx[rt] << endl;
	}
	
    return 0;
}