线段树30pts求助

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int mod = 998244353;
const int maxn = 2e5 + 10;

struct node{
	int l, r, sum, mx, lmx, rmx, tag;
}tree[maxn*4];

int n, Q, x, y, z, p, op;

void push_up(int i){
	tree[i].sum = tree[i*2].sum + tree[i*2+1].sum;
	tree[i].mx = max(tree[i*2].rmx + tree[i*2+1].lmx, max(tree[i*2].mx, tree[i*2+1].mx));
	if(tree[i*2].mx == tree[i*2].r - tree[i*2].l + 1) tree[i].lmx = tree[i*2].mx + tree[i*2+1].lmx;
	else tree[i].lmx = tree[i*2].lmx;
	if(tree[i*2+1].mx == tree[i*2+1].r - tree[i*2+1].l + 1) tree[i].rmx = tree[i*2+1].mx + tree[i*2].rmx;
	else tree[i].rmx = tree[i*2+1].rmx;
}

void build(int i, int l, int r){
	tree[i].l = l, tree[i].r = r, tree[i].tag = -1;
	if(l == r){
		tree[i].sum = 1;
		return;
	}
	int mid = l + r >> 1;
	build(i * 2, l, mid);
	build(i * 2 + 1, mid + 1, r);
	push_up(i);
}

void push_down(int i){
	if(tree[i].tag != -1){
		if(tree[i].tag){
			tree[i*2].sum = tree[i*2].r - tree[i*2].l + 1;
			tree[i*2].lmx = tree[i*2].rmx = tree[i*2].mx = 0;
			tree[i*2+1].sum = tree[i*2+1].r - tree[i*2+1].l + 1;
			tree[i*2+1].lmx = tree[i*2+1].rmx = tree[i*2+1].mx = 0;
		}
		else{
			tree[i*2].sum = 0;
			tree[i*2].lmx = tree[i*2].rmx = tree[i*2].mx = tree[i*2].r - tree[i*2].l + 1;
			tree[i*2+1].sum = 0;
			tree[i*2+1].lmx = tree[i*2+1].rmx = tree[i*2+1].mx = tree[i*2+1].r - tree[i*2+1].l + 1;
		}
		tree[i*2].tag = tree[i*2+1].tag = tree[i].tag;
		tree[i].tag = -1;
	}
}

void update(int i, int x, int y, int z){
	int l = tree[i].l, r = tree[i].r;
	if(x <= l && r <= y){
		if(z){
			tree[i].sum = r - l + 1;
			tree[i].lmx = tree[i].rmx = tree[i].mx = 0;
		}
		else{
			tree[i].sum = 0;
			tree[i].lmx = tree[i].rmx = tree[i].mx = r - l + 1;
		}
		tree[i].tag = z;
		return;
	}
	push_down(i);
	int mid = l + r >> 1;
	if(mid >= x) update(i * 2, x, y, z);
	if(mid < y) update(i * 2 + 1, x, y, z);
	push_up(i);
}

node query(int i, int x, int y){
	int l = tree[i].l, r = tree[i].r;
	if(x <= l && r <= y) return tree[i];
	push_down(i);
	int mid = l + r >> 1;
	if(mid >= y) return query(i * 2, x, y);
	if(mid < x) return query(i * 2 + 1, x, y);
	node L = query(i * 2, x, y), R = query(i * 2 + 1, x, y), res;
	res.sum = L.sum + R.sum;
	res.mx = max(L.rmx + R.lmx, max(L.mx, R.mx));
	if(L.lmx == L.r - L.l + 1) res.lmx = L.lmx + R.lmx;
	else res.lmx = L.lmx;
	if(R.rmx == R.r - L.l + 1) res.rmx = R.rmx + L.rmx;
	else res.rmx = R.rmx;
	return res;
}

void change(int l0, int r0, int l1, int r1){
	int num = query(1, l0, r0).sum;
	if(!num) return;
	update(1, l0, r0, 0);	
	int l = l1, r = r1;
	while(l < r){
		int mid = l + r + 1 >> 1;
		if(mid - l1 + 1 - query(1, l1, mid).sum <= num) l = mid;
		else r = mid - 1;
	}
	update(1, l1, l, 1);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> Q;
	build(1, 1, n);
	while(Q--){
		cin >> op;
		if(op == 0){
			cin >> x >> y;
			update(1, x, y, 0);
		}
		else if(op == 1){
			cin >> x >> y >> z >> p;
			change(x, y, z, p);
		}
		else{
			cin >> x >> y;
			cout << query(1, x, y).mx << endl;
		}
	}
	return 0;
}