萌新求调线段树/kel 悬关

// Problem: P2572 [SCOI2010] 序列操作
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2572
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define ll long long
#define inf 2000000000
using namespace std;

int read()
{
	int num = 0, w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
	while(ch <= '9' && ch >= '0') { num = (num << 3) + (num << 1) + (ch - '0'); ch = getchar(); }
	return num * w;
}

ll readll()
{
	ll num = 0, w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
	while(ch <= '9' && ch >= '0') { num = (num << 3) + (num << 1) + (ch - '0'); ch = getchar(); }
	return num * w;
}
/*
__int128 read128()
{
	__int128 num = 0, w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
	while(ch <= '9' && ch >= '0') { num = (num << 3) + (num << 1) + (ch - '0'); ch = getchar(); }
	return num * w;
}

void print(__int128 n)
{
    if(n < 0)
    {
        putchar('-');
        n *= -1;
    }
    if(n > 9) print(n / 10);
    putchar(n % 10 + '0');
}
上面不用看*/
#define MAXn 100010
#define MAXm 100010
int n, m;
int a[MAXn];

struct SegmentTree
{
	int l, r, ls, rs;
	int num1, num0;
	int lnum1, rnum1;
	int lnum0, rnum0;
	int max1, max0;
	int flag0, flag1, flag2;
} tr[MAXn << 2];

void pushup(int x)
{
	int ls = tr[x].ls, rs = tr[x].rs;
	
	tr[x].num1 = tr[ls].num1 + tr[rs].num1;
	tr[x].num0 = tr[ls].num0 + tr[rs].num0;
	
	if(tr[ls].num0 == 0)
		tr[x].lnum1 = tr[ls].num1 + tr[rs].lnum1;
	else tr[x].lnum1 = tr[ls].lnum1;
	if(tr[ls].num1 == 0)
		tr[x].lnum0 = tr[ls].num0 + tr[rs].lnum0;
	else tr[x].lnum0 = tr[ls].lnum0;
	
	
	if(tr[rs].num0 == 0)
		tr[x].rnum1 = tr[rs].num1 + tr[ls].rnum1;
	else tr[x].rnum1 = tr[rs].rnum1;
	if(tr[ls].num1 == 0)
		tr[x].rnum0 = tr[rs].num0 + tr[ls].rnum0;
	else tr[x].rnum0 = tr[rs].rnum0;
	
	tr[x].max1 = max({tr[ls].max1, tr[rs].max1, tr[ls].rnum1 + tr[rs].lnum1});
	tr[x].max0 = max({tr[ls].max0, tr[rs].max0, tr[ls].rnum0 + tr[rs].lnum0});
}

void pushdown(int id)
{
	if(tr[id].flag0)
	{
		int x = tr[id].ls;
		tr[x].flag0 = 1;
		tr[x].flag1 = 0, tr[x].flag2 = 0;
		tr[x].num0 = tr[x].r - tr[x].l + 1;
		tr[x].num1 = 0;
			
		tr[x].lnum0 = tr[x].num0;
		tr[x].rnum0 = tr[x].num0;
			
		tr[x].lnum1 = 0;
		tr[x].rnum1 = 0;
			
		tr[x].max0 = tr[x].num0;
		tr[x].max1 = 0;
		
		x = tr[id].rs;
		tr[x].flag0 = 1;
		tr[x].flag1 = 0, tr[x].flag2 = 0;
		tr[x].num0 = tr[x].r - tr[x].l + 1;
		tr[x].num1 = 0;
			
		tr[x].lnum0 = tr[x].num0;
		tr[x].rnum0 = tr[x].num0;
			
		tr[x].lnum1 = 0;
		tr[x].rnum1 = 0;
			
		tr[x].max0 = tr[x].num0;
		tr[x].max1 = 0;
		
		tr[id].flag0 = tr[id].flag1 = tr[id].flag2 = 0;
	}
	else if(tr[id].flag1)
	{
		int x = tr[id].ls;
		tr[x].flag1 = 1;
		tr[x].flag0 = 0, tr[x].flag2 = 0;
		tr[x].num1 = tr[x].r - tr[x].l + 1;
		tr[x].num0 = 0;
			
		tr[x].lnum1 = tr[x].num1;
		tr[x].rnum1 = tr[x].num1;
			
		tr[x].lnum0 = 0;
		tr[x].rnum0 = 0;
			
		tr[x].max1 = tr[x].num1;
		tr[x].max0 = 0;
		
		x = tr[x].rs;
		tr[x].flag1 = 1;
		tr[x].flag0 = 0, tr[x].flag2 = 0;
		tr[x].num1 = tr[x].r - tr[x].l + 1;
		tr[x].num0 = 0;
			
		tr[x].lnum1 = tr[x].num1;
		tr[x].rnum1 = tr[x].num1;
			
		tr[x].lnum0 = 0;
		tr[x].rnum0 = 0;
			
		tr[x].max1 = tr[x].num1;
		tr[x].max0 = 0;
		
		tr[id].flag0 = tr[id].flag1 = tr[id].flag2 = 0;
	}
	if(tr[id].flag2)
	{
		int x = tr[id].ls;
		tr[x].flag2 ^= 1;
		swap(tr[x].num1, tr[x].num0);
		swap(tr[x].max1, tr[x].max0);
		swap(tr[x].lnum1, tr[x].lnum0);
		swap(tr[x].rnum1, tr[x].rnum0);
		
		x = tr[id].rs;
		tr[x].flag2 ^= 1;
		swap(tr[x].num1, tr[x].num0);
		swap(tr[x].max1, tr[x].max0);
		swap(tr[x].lnum1, tr[x].lnum0);
		swap(tr[x].rnum1, tr[x].rnum0);
	}
	tr[id].flag0 = 0, tr[id].flag1 = 0, tr[id].flag2 = 0;
}

void build(int x, int L, int R)
{
	tr[x].l = L, tr[x].r = R;
	if(L == R)
	{
		if(a[L] == 1)
		{
			tr[x].num1 = 1;
			tr[x].lnum1 = 1;
			tr[x].rnum1 = 1;
			tr[x].max1 = 1;
		}
		else
		{
			tr[x].num0 = 1;
			tr[x].lnum0 = 1;
			tr[x].rnum0 = 1;
			tr[x].max0 = 1;
		}
		return;
	}
	int mid = (L + R) >> 1;
	tr[x].ls = x << 1;
	tr[x].rs = x << 1 | 1;
	build(tr[x].ls, L, mid);
	build(tr[x].rs, mid + 1, R);
	pushup(x);
}

void change(int opt, int x, int L, int R)
{
	if(tr[x].l >= L && tr[x].r <= R)
	{
		if(opt == 0)
		{
			tr[x].flag0 = 1;
			tr[x].flag1 = 0, tr[x].flag2 = 0;
			tr[x].num0 = tr[x].r - tr[x].l + 1;
			tr[x].num1 = 0;
			
			tr[x].lnum0 = tr[x].num0;
			tr[x].rnum0 = tr[x].num0;
			
			tr[x].lnum1 = 0;
			tr[x].rnum1 = 0;
			
			tr[x].max0 = tr[x].num0;
			tr[x].max1 = 0;
		}
		else if(opt == 1)
		{
			tr[x].flag1 = 1;
			tr[x].flag0 = 0, tr[x].flag2 = 0;
			tr[x].num1 = tr[x].r - tr[x].l + 1;
			tr[x].num0 = 0;
			
			tr[x].lnum1 = tr[x].num1;
			tr[x].rnum1 = tr[x].num1;
			
			tr[x].lnum0 = 0;
			tr[x].rnum0 = 0;
			
			tr[x].max1 = tr[x].num1;
			tr[x].max0 = 0;
		}
		else if(opt == 2)
		{
			tr[x].flag2 ^= 1;
			swap(tr[x].num1, tr[x].num0);
			swap(tr[x].max1, tr[x].max0);
			swap(tr[x].lnum1, tr[x].lnum0);
			swap(tr[x].rnum1, tr[x].rnum0);
		}
		return;
	}
	pushdown(x);
	int mid = (tr[x].l + tr[x].r) >> 1;
	if(L <= mid) change(opt, tr[x].ls, L, R);
	if(R >= mid + 1) change(opt, tr[x].rs, L, R);
	pushup(x);
}

SegmentTree ask(int opt, int x, int L, int R)
{
	if(tr[x].l >= L && tr[x].r <= R)
		return tr[x];
	pushdown(x);
	SegmentTree lres;
	bool flag = 0;
	int mid = (tr[x].l + tr[x].r) >> 1;
	if(L <= mid) lres = ask(opt, tr[x].ls, L, R), flag = 1;
	if(R >= mid + 1)
	{
		auto rres = ask(opt, tr[x].rs, L, R);
		if(!flag)
		{
			return rres;
		}
		if(opt == 3)
		{
			lres.num1 += rres.num1;
			return lres;
		}
		else
		{
			SegmentTree res;
	
			res.num1 = lres.num1 + rres.num1;
			res.num0 = lres.num0 + rres.num0;
	
			if(lres.num0 == 0)
				res.lnum1 = lres.num1 + rres.lnum1;
			else res.lnum1 = lres.lnum1;
			if(lres.num1 == 0)		
				res.lnum0 = lres.num0 + rres.lnum0;
			else res.lnum0 = lres.lnum0;
	
	
			if(rres.num0 == 0)
				res.rnum1 = rres.num1 + lres.rnum1;
			else res.rnum1 = rres.rnum1;
			if(lres.num1 == 0)
				res.rnum0 = rres.num0 + lres.rnum0;
			else res.rnum0 = rres.rnum0;
	
			res.max1 = max({lres.max1, rres.max1, res.lnum1, res.rnum1, lres.rnum1 + rres.lnum1});
			res.max0 = max({lres.max0, rres.max0, res.lnum0, res.rnum0, lres.rnum0 + rres.lnum0});
			res.l = lres.l, res.r = rres.r;
			return res;
		}
	}
	return lres;
}

void work()
{
	n = read(), m = read();
	for(int i = 1; i <= n; i++)
		a[i] = read();
	build(1, 1, n);
	while(m--)
	{
		int opt = read(), l = read(), r = read();
		l++, r++;
		if(opt < 3) change(opt, 1, l, r);
		else if(opt == 3) printf("%d\n", ask(opt, 1, l, r).num1);
		else if(opt == 4) printf("%d\n", ask(opt, 1, l, r).max1);
	}
	return;
}

int main()
{
	int T = 1;
	while(T--)
	{
		work();
	}
	return 0;
}