玄关 fhq-treap 20pts MLE 求调
查看原帖
玄关 fhq-treap 20pts MLE 求调
1067449
Chillturtle楼主2024/7/13 16:07
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010;
struct tree {
	int l;
	int r;
	int val;
	int pro;
	int sum;
	int tag;
	int maxn, Add;
} Tree[N];
void pushdown(int pos) {
	if (Tree[pos].tag != 0) {
		Tree[Tree[pos].l].tag ^= 1;
		Tree[Tree[pos].r].tag ^= 1;
		swap(Tree[pos].l, Tree[pos].r);
		Tree[pos].tag = 0;
	}
}
int rt = 0, tot;
int new_point(int pos) {
	Tree[++tot].val = pos;
	Tree[tot].sum = 1;
	Tree[tot].pro = rand();
	return tot;
}
void pushup(int k) {
	Tree[k].sum = Tree[Tree[k].l].sum + Tree[Tree[k].r].sum + 1;
}
void split(int pos, int k, int &p1, int &p2) {
	if (pos == 0) {
		p1 = p2 = 0;
	} else {
		pushdown(pos);
		int ln = Tree[Tree[pos].l].sum;
		if (ln < k) {
			p1 = pos;
			split(Tree[pos].r, k - ln - 1, Tree[p1].r, p2);
		} else {
			p2 = pos;
			split(Tree[pos].l, k, p1, Tree[p2].l);
		}
		pushup(pos);
	}
}
int merge(int l, int r) {
	if (l == 0 || r == 0) {
		return l | r;
	}
	pushdown(l);
	pushdown(r);
	if (Tree[l].pro >= Tree[r].pro) {
		Tree[l].r = merge(Tree[l].r, r);
		pushup(l);
		return l;
	} else {
		Tree[r].l = merge(l, Tree[r].l);
		pushup(r);
		return r;
	}
}
void reverse(int l, int r) {
	int p1 = 0, p2 = 0, p3 = 0, p4 = 0;
	split(rt, r, p1, p2);
	split(p1, l - 1, p3, p4);
	Tree[p4].tag ^= 1;
	p1 = merge(p3, p4);
	p2 = merge(p1, p2);
}
void insert(int xx) {
	int L, R;
	split(rt, xx - 1, L, R);
	rt = merge(merge(L, new_point(xx)), R);
}
void add(int l, int r, int val) {
	int x, y, z;
	split(rt, l - 1, x, y);
	split(y, r - l + 1, x, z);
	Tree[y].maxn += val;
	Tree[y].Add += val;
	Tree[y].val += val;
	rt = merge(merge(x, y), z);
}
void query(int l, int r) {
	int x, y, z;
	split(rt, l - 1, x, y);
	split(y, r - l + 1, x, z);
	cout << Tree[y].maxn << endl;
	rt = merge(merge(x, y), z);
}
int cnt = 0, sum = 0, q = 0;
int n, m;
//int n;
signed main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	//srand(time(NULL));
	//cout<<endl;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		insert(0);
	}
	for (int i = 1; i <= m; i++) {
		int l, r, opt;
		cin >> opt;
		cin >> l >> r;
		if (opt == 1) {
			int cnt;
			cin >> cnt;
			add(l, r, cnt);
		} else if (opt == 2) {
			reverse(l, r);
		} else {
			query(l, r);
		}
	}
//	dfs(rt);
	return 0;
}
2024/7/13 16:07
加载中...