求助fhq treap 交一次一个分

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
	int x = 0, w = 1;
	char ch = getchar();
	while ((ch < '0' || ch > '9') && ch != '-')
		ch = getchar();
	if (ch == '-') {
		w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * w;
}
mt19937 rnd((unsigned long long)(new char )^(20060725+20060705));
inline int rd(int l,int r){
	return rnd()%(r-l+1)+l;
}
const int N = 1000000;
const int ran = 1e9 + 7;
short Rand = 1;
stack<int> bin;
struct Tag {
	int tag1, tag2;
	Tag operator +(const Tag &t)const {
		if (t.tag1!=100000)
			return {t.tag1, 0};
		if (tag1!=100000)
			return {tag1, 0};
		return {100000, tag2 ^ t.tag2};
	}
};
struct Node {
	int l, r, key, val, siz, sum, lmax, rmax, maxx;
	Tag tag;
} tree[N];
int root, n, m, tot, cnt, pos;
void apply(int now, Tag tag) {
	if (tag.tag1!=100000) {
		tree[now].val = tag.tag1;
		tree[now].sum = tree[now].siz * tag.tag1;;
		tree[now].lmax = tree[now].rmax = tree[now].maxx = tag.tag1 > 0 ? tree[now].sum : tag.tag1;
		//		tree[now].tag.tag1 = 0;
	}
	if (tag.tag2) {
		swap(tree[now].l, tree[now].r);
		swap(tree[now].lmax, tree[now].rmax);
		//		tree[now].tag.tag2 = 0;
	}
}
void recycle(int x) {
	//	tree[x]={0,0,0,0,0,0,0,0,0,{0,0}};
	bin.push(x);
	if (tree[x].l)
		recycle(tree[x].l);
	if (tree[x].r)
		recycle(tree[x].r);
}
int use() {
	if (!bin.empty()) {
		int x = bin.top();
		bin.pop();
		return x;
	} else {
		++tot;
		//		cout<<"("<<tot<<")";
		return tot;
	}
}
void create(int &now, int x) {
	now = use();
	Rand *= ran;
	tree[now] = {0, 0, rd(-1e9,1e9), x, 1, x, x, x, x, {100000, 0}};
}
void pushup(int now) {
	Node l = tree[tree[now].l], r = tree[tree[now].r];
	tree[now].siz = l.siz + r.siz + 1;
	tree[now].sum = l.sum + r.sum + tree[now].val;
	tree[now].lmax = max(l.lmax, max(l.sum + tree[now].val, tree[now].val + l.sum + r.lmax));
	tree[now].rmax = max(r.rmax, max(r.sum + tree[now].val, tree[now].val + r.sum + l.rmax));
	tree[now].maxx = max(l.maxx, max(r.maxx, max(l.rmax + tree[now].val + r.lmax, max(l.sum + tree[now].val, r.sum + tree[now].val))));
	//	tree[now].maxx = max(l.maxx, max(r.maxx, l.rmax + tree[now].val + r.lmax));
}
void pushdown(int now) {
	if (tree[now].tag.tag1!=100000) {
		tree[tree[now].l].tag = tree[tree[now].l].tag + tree[now].tag;
		tree[tree[now].r].tag = tree[tree[now].r].tag + tree[now].tag;
		apply(tree[now].l, tree[now].tag);
		apply(tree[now].r, tree[now].tag);
		tree[now].tag.tag1 = 100000;
	}
	if (tree[now].tag.tag2) {
		tree[tree[now].l].tag = tree[tree[now].l].tag + tree[now].tag;
		tree[tree[now].r].tag = tree[tree[now].r].tag + tree[now].tag;
		apply(tree[now].l, tree[now].tag);
		apply(tree[now].r, tree[now].tag);
		tree[now].tag.tag2 = 0;
	}
}
void split(int now, int x, int &nowl, int &nowr) {
	//		cout<<now<<" "<<x<<" "<<nowl<<" "<<nowr<<endl;
	if (!now) {
		nowl = nowr = 0;
		return ;
	}
	pushdown(now);
	if (tree[tree[now].l].siz + 1 <= x) {
		nowl = now;
		//			cout<<endl<<now<<" "<<x<<" "<<nowl<<" "<<nowr<<endl;
		split(tree[now].r, x - tree[tree[now].l].siz - 1, tree[now].r, nowr);
		pushup(nowl);
	} else {
		nowr = now;
		//		cout<<endl<<now<<" "<<x<<" "<<nowl<<" "<<nowr<<endl;
		split(tree[now].l, x, nowl, tree[now].l);
		pushup(nowr);
	}
	//	pushup(now);
}
int merge(int nowl, int nowr) {
	if (!nowl || !nowr)
		return nowl | nowr;
	pushdown(nowl);
	pushdown(nowr);
	if (tree[nowl].key < tree[nowr].key) {
		tree[nowl].r = merge(tree[nowl].r, nowr);
		pushup(nowl);
		return nowl;
	}
	tree[nowr].l = merge(nowl, tree[nowr].l);
	pushup(nowr);
	return nowr;
}
void Insert() {
	int nowl = 0, nowr = 0, now = 0;
	pos = read();
	split(root, pos, nowl, nowr);
	//	cout<<tree[nowl].siz<<endl;
	//	cout <<nowl<<" "<<nowr<<" "<< tree[nowl].sum<<" "<< tree[nowl].siz<< endl;
	//	cout<<tree[tree[nowl].l].sum<<" "<<tree[tree[nowl].r].sum<<endl;
	cnt = read();
	if(cnt==0)
		return;
	for (int i = 1; i <= cnt; i++) {
		int x = read();
		create(now, x);
		//		split(root, pos + i - 2, nowl, nowr);
		//		root = merge(merge(nowl, now), nowr);
		nowl = merge(nowl, now);
		//		cout<<tree[nowl].sum<<" "<<tree[nowl].maxx<<endl;
	}
	//	cout<<tree[nowl].sum<<endl;
	root = merge(nowl, nowr);
	//	cout<<tree[root].maxx<<endl;
}
void Delete() {
	pos = read();
	cnt = read();
	if(cnt==0)
		return ;
	int a, b, c;
	split(root, pos - 1, a, b);
	split(b, cnt, b, c);
	recycle(b);
	root = merge(a, c);
}
void Makesame() {
	int pos = read();
	cnt = read();
	if(cnt==0)
		return ;
	int C = read();
	int a, b, c;
	Tag tagg ;
	tagg.tag1 = C;
	tagg.tag2 = 0;
	split(root, pos - 1, a, b);
	split(b, cnt, b, c);
	tree[b].tag = tree[b].tag + tagg;
	apply(b, tagg);
	//	cout<<tagg.tag1<<endl;
	root = merge(merge(a, b), c);
}
void Reverse() {
	pos = read();
	cnt = read();
	if(cnt==0)
		return ;
	int a, b, c;
	Tag tagg = {100000, 1};
	split(root, pos - 1, a, b);
	split(b, cnt, b, c);
	tree[b].tag = tree[b].tag + tagg;
	apply(b, tagg);
	root = merge(merge(a, b), c);
}
void Getsum() {
	pos = read();
	cnt = read();
	if(cnt==0){
		cout<<0<<endl;
		return ;
	}
		
	int a, b, c;
	split(root, pos - 1, a, b);
	//	cout << tree[a].sum << endl;
	split(b, cnt, b, c);
	//	cout << tree[a].sum << " " << tree[b].sum << " " << tree[c].sum << endl;
	printf("%lld\n",tree[b].sum );
	//	cout << tree[b].sum << endl;
	root = merge(merge(a, b), c);
}
void Maxsum() {
	printf("%lld\n",tree[root].maxx);
	//	cout << tree[root].maxx << endl;
}
void dfs(int x) {
	pushdown(x);
	if (tree[x].l)
		dfs(tree[x].l);
	cout << tree[x].val << " ";
	if (tree[x].r)
		dfs(tree[x].r);
	return ;
}
signed main() {
	//		freopen("1.in","r",stdin);
	//		freopen("1.out","w",stdout);
	srand(time(0));
	n = read();
	m = read();
	int now, nowl, nowr;
	for (int i = 1; i <= n; i++) {
		int x = read();
		create(now, x);
		split(root, i - 1, nowl, nowr);
		root = merge(merge(nowl, now), nowr);
	}
	//	cout<<tree[4].sum<<" "<<tree[4].siz<<endl;
	//	for (int i = 1; i <= n; i++)
	//		cout << tree[i].val << " " << tree[i].sum << " " << tree[i].siz << " "<<tree[i].l<<" "<<tree[i].r<< endl;
	for (int i = 1; i <= m; i++) {
		string opt;
		cin >> opt;
		if (opt == "INSERT")
			Insert();
		//			cout<<tree[root].siz<<endl<<endl,Insert(),cout<<tree[root].siz<<endl;
		if (opt == "DELETE")
			Delete();
		//		cout<<tree[root].siz<<endl,Delete(),cout<<tree[root].siz<<endl;
		if (opt == "MAKE-SAME")
			Makesame();
		if (opt == "REVERSE")
			Reverse();
		if (opt == "GET-SUM")
			Getsum();
		if (opt == "MAX-SUM")
			Maxsum();
		//		dfs(root);
		//		cout << endl;
		//		cout << tree[root].sum << endl;
		//		Maxsum();
	}
	return 0;
}