0分求调

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 200005;

class SegmentTree {
public:
	struct Segment {
		int cnt0, cnt1;
		int lenL0, lenL1;
		int lenR0, lenR1;
		int len0, len1;
		int lo, hi;
	
		Segment(int cnt0 = 0, int cnt1 = 0, 
				int lenL0 = 0, int lenL1 = 0, 
				int lenR0 = 0, int lenR1 = 0, 
				int len0 = 0, int len1 = 0, 
				int lo = 0, int hi = 0):
		cnt0(cnt0), cnt1(cnt1), lenL0(lenL0), 
		lenL1(lenL1), lenR0(lenR0), lenR1(lenR1), 
		len0(len0), len1(len1), lo(lo), hi(hi) {}
		
		operator bool() {
			return cnt0 || cnt1 || lenL0 || 
				lenL1 || lenR0 || lenR1 || 
				len0 || len1 || lo || hi;
		}
	};
	Segment tree[MAXN << 3];
	int set[MAXN << 3], reverse[MAXN << 3]; 
	/* 线段树要开更大的空间！！！ */
	
	inline int ls(int i) { return i << 1; }
	inline int rs(int i) { return (i << 1) | 1; }
	
	inline Segment merge(Segment &A, Segment &B) {
		return Segment(
		A.cnt0 + B.cnt0, A.cnt1 + B.cnt1, 
		(A.cnt0 == (A.hi - A.lo + 1)) ? 
		A.cnt0 + B.lenL0 : A.lenL0, 
		(A.cnt1 == (A.hi - A.lo + 1)) ? 
		A.cnt1 + B.lenL1 : A.lenL1, 
		(B.cnt0 == (B.hi - B.lo + 1)) ? 
		B.cnt0 + A.lenR0 : B.lenR0, 
		(B.cnt1 == (B.hi - B.lo + 1)) ? 
		B.cnt1 + A.lenR1 : B.lenR1, 
		max(max(A.len0, B.len0), A.lenR0 + B.lenL0),
		max(max(A.len1, B.len1), A.lenR1 + B.lenL1),
		A.lo, B.hi
		);
	}
	
	inline void modify(int i, int mode) {
		int len = tree[i].hi - tree[i].lo + 1;
		if(mode == 0) { // set to 0
			set[i] = 0, reverse[i] = 0;
			tree[i] = Segment(
				len, 0, len, 0, len, 0, len, 0, 
				tree[i].lo, tree[i].hi
			);
		} else if(mode == 1) { // set to 1
			set[i] = 1, reverse[i] = 0;
			tree[i] = Segment(
				0, len, 0, len, 0, len, 0, len, 
				tree[i].lo, tree[i].hi
			);
		} else if(mode == 2) { // reverse
			reverse[i] ^= 1;
			swap(tree[i].cnt0, tree[i].cnt1);
			swap(tree[i].len0, tree[i].len1);
			swap(tree[i].lenL0, tree[i].lenL1);
			swap(tree[i].lenR0, tree[i].lenR1);
		}
	}
	
	inline void push_down(int i) {
		/*
		区间赋值操作优先级大于区间取反，
		因此要先取反，然后让赋值操作覆盖掉取反操作
		*/
		if(reverse[i]) {
			/* 注意每个序号对应的操作！ */
			modify(ls(i), 2);
			modify(rs(i), 2);
			reverse[i] = 0;
		}
		if(set[i] != -1) {
			modify(ls(i), set[i]);
			modify(rs(i), set[i]);
			set[i] = -1;
		}
	}
	
	void build(int* a, int lo, int hi, int i = 1) {
		set[i] = -1, reverse[i] = 0;
		if(lo == hi) {
			int t = a[lo];
			tree[i] = Segment(!t, t, !t, t, !t, t, 
								!t, t, lo, hi);
			return;
		}
		int mid = lo + ((hi - lo) >> 1);
		build(a, lo, mid, ls(i));
		build(a, mid + 1, hi, rs(i));
		tree[i] = merge(tree[ls(i)], tree[rs(i)]);
	}
	
	void update(int s, int t, int mode, int i = 1) {
		/* 在每次递归调用的起始处检查，
		减少 mid 的计算开销 */
		if(t < tree[i].lo || s > tree[i].hi) return;
		if(s <= tree[i].lo && tree[i].hi <= t) {
			modify(i, mode); return;
		}
		push_down(i);
		/* lo, hi 是查询区间，不是子节点的区间！！ 
		因此递归时传参要把查询区间原封不动地传过去！
		*/
		update(s, t, mode, ls(i));
		update(s, t, mode, rs(i));
		tree[i] = merge(tree[ls(i)], tree[rs(i)]);
	}
	
	Segment query(int s, int t, int i = 1) {
		if(s <= tree[i].lo && tree[i].hi <= t)
			return tree[i];
		push_down(i);
		int mid = tree[i].lo + 
				((tree[i].hi - tree[i].lo) >> 1);
		Segment A, B;
		if(s <= mid) A = query(s, mid, ls(i));
		if(t > mid) B = query(mid + 1, t, rs(i));
		if(A && B) return merge(A, B);
		return A ? A : B;
	}
};

int n, m, op, l, r, a[MAXN << 1];
SegmentTree st;

int main() {
	scanf("%d%d", &n, &m);
	/* 这道题的下标是 0-indexed 的！！！*/
	for(int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	st.build(a, 0, n - 1);
	while(m--) {
		scanf("%d%d%d", &op, &l, &r);
		if(op < 3) st.update(l, r, op);
		else if(op == 3)
			printf("%d\n", st.query(l, r).cnt1);
		else if(op == 4)
			printf("%d\n", st.query(l, r).len1);
	}
	return 0;
}