线段树板求条

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

bool st;

const int N = 1e5 + 5;

int n, m, a[N];

struct Seg {
	int siz, sum1;
	int tag1, tag2, tag3;
	int lt0, rt0, ret0, lt1, rt1, ret1;
	
	Seg () { siz = sum1 = tag1 = tag2 = tag3 = lt0 = rt0 = ret0 = lt1 = rt1 = ret1 = 0; }
} tree[N << 2];

Seg merge (Seg x, Seg y) {
	Seg z;
	z.siz = x.siz + y.siz;
	z.sum1 = x.sum1 + y.sum1;
	z.lt0 = x.lt0;
	if (x.sum1 == 0) z.lt0 = x.siz + y.lt0;
	z.rt0 = y.rt0;
	if (y.sum1 == 0) z.rt0 = y.siz + x.rt0;
	z.ret0 = max ({x.ret0, y.ret0, x.rt0 + y.lt0});
	z.lt1 = x.lt1;
	if (x.sum1 == x.siz) z.lt1 = x.siz + y.lt1;
	z.rt1 = y.rt1;
	if (y.sum1 == y.siz) z.rt1 = y.siz + x.rt1;
	z.ret1 = max ({x.ret1, y.ret1, x.rt1 + y.lt1});
	return z;
}

void pushup (int node) { tree[node] = merge (tree[node << 1], tree[(node << 1) + 1]); }

void pushdown (int node) {
	int ls = node << 1, rs = (node << 1) + 1;
	if (tree[node].tag3) {
		tree[node].sum1 = tree[node].siz - tree[node].sum1;
		swap (tree[node].tag1, tree[node].tag2);
		swap (tree[node].lt0, tree[node].lt1); 
		swap (tree[node].rt0, tree[node].rt1); 
		swap (tree[node].ret0, tree[node].ret1);
		tree[ls].tag3 ^= 1, tree[rs].tag3 ^= 1;
		tree[node].tag3 = 0;
	} 
	if (tree[node].tag1) {
		tree[ls].sum1 = tree[rs].sum1 = 0;
		tree[ls].lt0 = tree[ls].rt0 = tree[ls].ret0 = tree[ls].siz;
		tree[rs].lt0 = tree[rs].rt0 = tree[rs].ret0 = tree[rs].siz;
		tree[ls].lt1 = tree[ls].rt1 = tree[ls].ret1 = tree[rs].lt1 = tree[rs].rt1 = tree[rs].ret1 = 0;
		tree[ls].tag1 = 1, tree[rs].tag1 = 1;
		tree[node].tag1 = 0;
	}
	if (tree[node].tag2) {
		tree[ls].sum1 = tree[ls].siz, tree[rs].sum1 = tree[rs].siz;
		tree[ls].lt1 = tree[ls].rt1 = tree[ls].ret1 = tree[ls].siz;
		tree[rs].lt1 = tree[rs].rt1 = tree[rs].ret1 = tree[rs].siz;
		tree[ls].lt0 = tree[ls].rt0 = tree[ls].ret0 = tree[rs].lt0 = tree[rs].rt0 = tree[rs].ret0 = 0;
		tree[ls].tag2 = 1, tree[rs].tag2 = 1;
		tree[node].tag2 = 0;
	}
}

void build (int node, int l, int r) {
	if (l == r) {
		tree[node].siz = 1; tree[node].sum1 = a[l];
		tree[node].lt0 = tree[node].rt0 = tree[node].ret0 = 1 - a[l];
		tree[node].lt1 = tree[node].rt1 = tree[node].ret1 = a[l];
		return ;
	}
	
	int mid = l + ((r - l) >> 1);
	build (node << 1, l, mid);
	build ((node << 1) + 1, mid + 1, r);
	pushup (node);
} 

void modify1 (int node, int l, int r, int s, int t) {
	pushdown (node);
	if (s <= l && r <= t) {
		tree[node].sum1 = 0;
		tree[node].lt0 = tree[node].rt0 = tree[node].ret0 = r - l + 1;
		tree[node].lt1 = tree[node].rt1 = tree[node].ret1 = 0;
		tree[node].tag1 = 1;
		return ;
	}
	
	int mid = l + ((r - l) >> 1);
	if (s <= mid) modify1 (node << 1, l, mid, s, t);
	if (t > mid) modify1 ((node << 1) + 1, mid + 1, r, s, t);
	pushup (node);
}

void modify2 (int node, int l, int r, int s, int t) {
	pushdown (node);
	if (s <= l && r <= t) {
		tree[node].sum1 = r - l + 1;
		tree[node].lt0 = tree[node].rt0 = tree[node].ret0 = 0;
		tree[node].lt1 = tree[node].rt1 = tree[node].ret1 = r - l + 1;
		tree[node].tag2 = 1;
		return ;
	}
	
	int mid = l + ((r - l) >> 1);
	if (s <= mid) modify2 (node << 1, l, mid, s, t);
	if (t > mid) modify2 ((node << 1) + 1, mid + 1, r, s, t);
	pushup (node);
}

void modify3 (int node, int l, int r, int s, int t) {
	pushdown (node);
	if (s <= l && r <= t) {
		tree[node].tag3 ^= 1;
		return ;
	}
	
	int mid = l + ((r - l) >> 1);
	if (s <= mid) modify3 (node << 1, l, mid, s, t);
	if (t > mid) modify3 ((node << 1) + 1, mid + 1, r, s, t);
	pushup (node);
}

int query (int node, int l, int r, int s, int t) {
	pushdown (node);
	if (s <= l && r <= t) return tree[node].sum1;
	
	int mid = l + ((r - l) >> 1), ret = 0;
	if (s <= mid) ret += query (node << 1, l, mid, s, t);
	if (t > mid) ret += query ((node << 1) + 1, mid + 1, r, s, t);
	return ret;
}

Seg query2 (int node, int l, int r, int s, int t) {
	pushdown (node);
	if (s <= l && r <= t) return tree[node];
	
	int mid = l + ((r - l) >> 1);
	if (t <= mid) return query2 (node << 1, l, mid, s, t);
	if (s > mid) return query2 ((node << 1) + 1, mid + 1, r, s, t);
	Seg L = query2 (node << 1, l, mid, s, t), R = query2 ((node << 1) + 1, mid + 1, r, s, t);
	return merge (L, R);
}

bool ed;

int main () {

	ios::sync_with_stdio (false);
	cin.tie (0); cout.tie (0);
	
	cerr << "[Memory] " << (&st - &ed) / 1024 / 1024 << " MB\n";
	
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	
	build (1, 1, n);
	while (m--) {
		int opt, l, r;
		cin >> opt >> l >> r;
		l++, r++;
		
		if (opt == 0) modify1 (1, 1, n, l, r);
		else if (opt == 1) modify2 (1, 1, n, l, r);
		else if (opt == 2) modify3 (1, 1, n, l, r);
		else if (opt == 3) cout << query (1, 1, n, l, r) << '\n';
		else cout << query2 (1, 1, n, l, r).ret1 << '\n';
		
//		for (int i = 1; i <= n; ++i) cout << query (1, 1, n, i, i) << ' ';
//		cout << '\n';
	}
	
	return 0;
}
/*
10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
1 1 1 1 1 0 1 0 1 1
3 0 5
5
2 2 2
1 1 0 1 1 0 1 0 1 1
4 0 4
2
0 3 6
1 1 0 0 0 0 0 0 1 1
2 3 7
1 1 0 1 1 1 1 1 1 1
4 2 8
6
1 0 5
1 1 1 1 1 1 1 1 1 1
0 5 6
1 1 1 1 1 0 0 1 1 1
3 3 9
5

5 5
0 0 1 0 0
2 0 4
4 0 4
2 0 1
3 0 4
4 0 4
*/