线段树求调 0pts

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int now=0,nev=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')nev=-1;c=getchar();}
	while(c>='0'&&c<='9'){now=(now<<1)+(now<<3)+(c&15);c=getchar(); }
	return now*nev;
}

#define ls(x) x * 2
#define rs(x) x * 2 + 1
#define range(x) t[x].r - t[x].l + 1

const int N = 5e5 + 5;
struct Node{
	int l, r;
	int pre0, suf0, pre1, suf1;
	int dat0, dat1;
	int sum, r0, r1, r2;
} t[N << 2];
int a[N];
int n, m;

void push_up(int x){
	t[x].sum = t[ls(x)].sum + t[rs(x)].sum;
	t[x].pre0 = t[ls(x)].pre0;
	if (t[ls(x)].pre0 == range(ls(x)))
		t[x].pre0 = t[ls(x)].pre0 + t[rs(x)].pre0;
	t[x].pre1 = t[ls(x)].pre1;
	if (t[ls(x)].pre1 == range(ls(x)))
		t[x].pre1 = t[ls(x)].pre1 + t[rs(x)].pre1;
	t[x].suf0 = t[rs(x)].suf0;
	if (t[rs(x)].suf0 == range(rs(x)))
		t[x].suf0 = t[ls(x)].suf0 + t[rs(x)].suf0;
	t[x].suf1 = t[rs(x)].suf1;
	if (t[rs(x)].suf1 == range(rs(x)))
		t[x].suf1 = t[ls(x)].suf1 + t[rs(x)].suf1;
	t[x].dat1 = max({t[ls(x)].dat1, t[rs(x)].dat1, t[ls(x)].suf1 + t[rs(x)].pre1});
	t[x].dat0 = max({t[ls(x)].dat0, t[rs(x)].dat0, t[ls(x)].suf0 + t[rs(x)].pre0});
}

void push_down(int x){
	if (t[x].r0){
		t[ls(x)].r0 = t[rs(x)].r0 = 1;
		t[ls(x)].sum = t[rs(x)].sum = 0;
		t[ls(x)].pre0 = t[ls(x)].suf0 = range(ls(x));
		t[ls(x)].suf1 = t[ls(x)].pre1 = 0;
		t[rs(x)].pre0 = t[rs(x)].suf0 = range(rs(x));
		t[rs(x)].suf1 = t[rs(x)].pre1 = 0;
		t[ls(x)].dat0 = range(ls(x));
		t[rs(x)].dat0 = range(rs(x));
		t[ls(x)].dat1 = t[rs(x)].dat1 = 0;
		t[x].r0 = 0;
	}
	if (t[x].r1){
		t[ls(x)].r1 = t[rs(x)].r1 = 1;
		t[ls(x)].sum = range(ls(x));
		t[rs(x)].sum = range(rs(x));
		t[ls(x)].pre1 = t[ls(x)].suf1 = range(ls(x));
		t[ls(x)].suf0 = t[ls(x)].pre0 = 0;
		t[rs(x)].pre1 = t[rs(x)].suf1 = range(rs(x));
		t[rs(x)].suf0 = t[rs(x)].pre0 = 0;
		t[ls(x)].dat1 = range(ls(x));
		t[rs(x)].dat1 = range(rs(x));
		t[ls(x)].dat0 = t[rs(x)].dat0 = 0;
		t[x].r1 = 0;
	}
	if (t[x].r2){
		t[ls(x)].r2 ^= 1, t[rs(x)].r1 ^= 1;
		swap(t[ls(x)].pre0, t[ls(x)].pre1);
		swap(t[ls(x)].suf0, t[ls(x)].suf1);
		swap(t[rs(x)].pre0, t[rs(x)].pre1);
		swap(t[rs(x)].suf0, t[rs(x)].suf1);
		swap(t[ls(x)].dat0, t[ls(x)].dat1);
		swap(t[rs(x)].dat0, t[rs(x)].dat1);
		t[ls(x)].sum = range(ls(x)) - t[ls(x)].sum;
		t[rs(x)].sum = range(rs(x)) - t[rs(x)].sum;
		t[x].r2 = 0;
	}
}

void build(int x, int l, int r){
	t[x].l = l, t[x].r = r;
	if (l == r){
		if (a[l] == 0){
			t[x].suf0 = t[x].pre0 = 1;
			t[x].suf1 = t[x].pre1 = 0;
			t[x].sum = t[x].dat1 = 0;
			t[x].dat0 = 1;
		}
		else{
			t[x].suf1 = t[x].pre1 = 1;
			t[x].suf0 = t[x].pre0 = 0;
			t[x].sum = t[x].dat1 = 1;
			t[x].dat0 = 0;
		}
		return ;
	}
	int mid = (l + r) >> 1;
	build(ls(x), l, mid);
	build(rs(x), mid + 1, r);
	push_up(x);
}

void update0(int x, int l, int r){
	if (l <= t[x].l && t[x].r <= r){
		t[x].sum = 0;
		t[x].r0 = 1, t[x].r1 = 0;
		t[x].pre0 = t[x].suf0 = range(x);
		t[x].suf1 = t[x].pre1 = t[x].dat1 = 0;
		t[x].dat0 = range(x);
		return ;
	}
	push_down(x);
	int mid = (t[x].l + t[x].r) >> 1;
	if (l <= mid) update0(ls(x), l, r);
	if (r > mid) update0(rs(x), l, r);
	push_up(x); 
}

void update1(int x, int l, int r){
	if (l <= t[x].l && t[x].r <= r){
		t[x].sum = range(x);
		t[x].r1 = 1, t[x].r0 = 0;
		t[x].pre0 = t[x].suf0 = 0;
		t[x].pre1 = t[x].suf1 = t[x].dat1 = range(x);
		t[x].dat0 = 0;
		return ;
	}
	push_down(x); 
	int mid = (t[x].l + t[x].r) >> 1;
	if (l <= mid) update1(ls(x), l, r);
	if (r > mid) update1(rs(x), l, r);
	push_up(x);
}

void update2(int x, int l, int r){
	if (l <= t[x].l && t[x].r <= r){
		swap(t[x].suf0, t[x].suf1);
		swap(t[x].pre0, t[x].pre1);
		swap(t[x].dat0, t[x].dat1);
		t[x].r2 ^= 1;
		return ;
	}
	push_down(x); 
	int mid = (t[x].l + t[x].r) >> 1;
	if (l <= mid) update2(ls(x), l, r);
	if (r > mid) update2(rs(x), l, r);
	push_up(x); 
}

int query3(int x, int l, int r){
	if (l <= t[x].l && t[x].r <= r) return t[x].sum;
	push_down(x);
	int mid = (t[x].l + t[x].r) >> 1;
	int val = 0;
	if (l <= mid) val += query3(ls(x), l, r);
	if (r > mid) val += query3(rs(x), l, r);
	return val; 
}

Node query4(int x, int l, int r){
	if (l <= t[x].l && t[x].r <= r) return t[x];
	int mid = (t[x].l + t[x].r) >> 1;
	if (l <= mid && r > mid){
		auto lson = query4(ls(x), l, r);
		auto rson = query4(rs(x), l, r);
		Node ans;
		ans.l = lson.l, ans.r = rson.r;
		ans.pre1 = max(lson.pre1, lson.sum + rson.pre1);
		ans.suf1 = max(rson.suf1, rson.sum + lson.suf1);
		ans.dat1 = max({lson.dat1, rson.dat1, lson.suf1 + rson.pre1});
		ans.pre0 = max(lson.pre0, lson.sum + rson.pre0);
		ans.suf0 = max(rson.suf0, rson.sum + lson.suf0);
		ans.dat0 = max({lson.dat0, rson.dat0, lson.suf0 + rson.pre0});
	}
	else if (l <= mid) return query4(ls(x), l, r);
	else return query4(rs(x), l, r);
} 

signed main()
{
	n = read(), m = read();
	for (int i = 1; i <= n; i ++) a[i] = read();
	build(1, 1, n);
	while (m --){
		int op = read(), l = read() + 1, r = read() + 1;
		if (op == 0) update0(1, l, r);
		if (op == 1) update1(1, l, r);
		if (op == 2) update2(1, l, r);
		if (op == 3)
			cout << query3(1, l, r) << "\n";
		if (op == 4){
			auto tmp = query4(1, l, r);
			cout << tmp.dat1 << "\n";
		}
	} 
    return 0;
}