题目&&链接
思路
每一步操作线段树都是可以维护的
但是，合起来也确实太恶心了点
维护 区间和，1的最长连续，前缀连续，后缀连续，
以及0的最长连续，前缀连续，后缀连续
7个值
以及两个lazy
一个是区间赋值的lazy1，一个是取反的lazy2
然后码代码就好了
注意*1
lazy下方的时候
只有三种情况
①先下方lazy1，后lazy2
②下方lazy1
③下方lazy2
因为如果是区间赋值的话，那么lazy2不lazy2的也没有啥子意义了
所以先lazy2，后lazy1这三种是被覆盖的
所以我们先下方lazy1
再下方lazy2
注意*2
还有，就是那个维护前缀后缀这种东西的时候
询问范围值不是int
因为你的答案不一定在线段树的一个儿子中，不能二分
所以要返回node_seg再进行选择
注意*3
写长代码的时候，像我一样没有一遍过变异的能力而且报错极多的
最后写一段编译一段，要不最后真的很绝望的
那些许多重复操作的
最好写点小函数之类的
减轻代码量
我只会输出调试，算了，不说了
/**************************************************************
Problem: 1858
User: 3010651817
Language: C++
Result: Accepted
Time:1496 ms
Memory:20436 kb
****************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int maxn = 1e5 + 7;
int n, m, a[maxn];
struct node {
int l, r, size;
int lazy1 , lazy2;
int sum;
int lk, rk, k;
int lk_, rk_, k_;
void add(int a) {
lk = rk = k = sum = a;
}
void add_(int a) {
lk_ = rk_ = k_ = a;
sum = size - a;
}
void swap_() {
swap(k_, k);
swap(lk_, lk);
swap(rk_, rk);
sum = size - sum;
}
} e[maxn << 2];
void pushdown_lazy1(int rt) {
e[ls].add(e[rt].lazy1 * e[ls].size);
e[ls].add_((1 ^ e[rt].lazy1)*e[ls].size);
e[ls].lazy1 = e[rt].lazy1;
e[ls].lazy2 = 0;
e[rs].add(e[rt].lazy1 * e[rs].size);
e[rs].add_((1 ^ e[rt].lazy1)*e[rs].size);
e[rs].lazy1 = e[rt].lazy1;
e[rs].lazy2 = 0;
}
void pushdown_lazy2(int rt) {
e[ls].swap_();
e[ls].lazy2 = !e[ls].lazy2;
e[rs].swap_();
e[rs].lazy2 = !e[rs].lazy2;
}
int read() {
int x = 0, f = 1; char s = getchar();
for (; s < '0' || s > '9'; s = getchar()) if (s == '-') f = -1;
for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';
return x * f;
}
int max_2(int a, int b, int c) {
return max(max(a, b), c);
}
void pushup(int rt) {
e[rt].sum = e[ls].sum + e[rs].sum;
e[rt].k = max_2(e[ls].k, e[rs].k, e[ls].rk + e[rs].lk);
e[rt].lk = (e[ls].lk == e[ls].size) ? e[ls].lk + e[rs].lk : e[ls].lk;
e[rt].rk = (e[rs].rk == e[rs].size) ? e[ls].rk + e[rs].rk : e[rs].rk;
e[rt].k_ = max_2(e[ls].k_, e[rs].k_, e[ls].rk_ + e[rs].lk_);
e[rt].lk_ = (e[ls].lk_ == e[ls].size) ? e[ls].lk_ + e[rs].lk_ : e[ls].lk_;
e[rt].rk_ = (e[rs].rk_ == e[rs].size) ? e[ls].rk_ + e[rs].rk_ : e[rs].rk_;
}
void pushdown(int rt) {
if (e[rt].lazy1 != -1)
pushdown_lazy1(rt);
if (e[rt].lazy2 == 1)
pushdown_lazy2(rt);
e[rt].lazy1 = -1;
e[rt].lazy2 = 0;
}
void build(int l, int r, int rt) {
e[rt].l = l, e[rt].r = r, e[rt].size = r - l + 1;
e[rt].lazy1 = -1, e[rt].lazy2 = 0;
if (l == r) {
e[rt].add(a[l]);
e[rt].add_(!a[l]);
return;
}
int mid = (l + r) >> 1;
build(l, mid, ls);
build(mid + 1, r, rs);
pushup(rt);
}
void update_1(int L, int R, int k, int rt) {
if (L <= e[rt].l && e[rt].r <= R) {
e[rt].add(k * e[rt].size);
e[rt].add_((1 ^ k)*e[rt].size);
e[rt].lazy1 = k;
e[rt].lazy2 = 0;
return;
}
pushdown(rt);
int mid = (e[rt].l + e[rt].r) >> 1;
if (L <= mid) update_1(L, R, k, ls);
if (R > mid) update_1(L, R, k, rs);
pushup(rt);
}
void update_2(int L, int R, int rt) {
if (L <= e[rt].l && e[rt].r <= R) {
e[rt].swap_();
e[rt].lazy2 = !e[rt].lazy2;
return;
}
pushdown(rt);
int mid = (e[rt].l + e[rt].r) >> 1;
if (L <= mid) update_2(L, R, ls);
if (R > mid) update_2(L, R, rs);
pushup(rt);
}
int query_1(int L, int R , int rt) {
if (L <= e[rt].l && e[rt].r <= R) {
return e[rt].sum;
}
pushdown(rt);
int mid = (e[rt].l + e[rt].r) >> 1, ans = 0;
if (L <= mid) ans += query_1(L, R, ls);
if (R > mid) ans += query_1(L, R, rs);
pushup(rt);
return ans;
}
node query_2(int L, int R, int rt) {
if (L <= e[rt].l && e[rt].r <= R) {
return e[rt];
}
pushdown(rt);
int mid = (e[rt].l + e[rt].r) >> 1;
if (L <= mid && R > mid) {
node a = query_2(L, R, ls) , b = query_2(L, R, rs);
node tmp = {};
tmp.k = max_2(a.k, b.k, a.rk + b.lk);
tmp.lk = (a.lk == a.size) ? a.lk + b.lk : a.lk;
tmp.rk = (b.rk == b.size) ? a.rk + b.rk : b.rk;
return tmp;
} else if (L <= mid) return query_2(L, R, ls);
else if (R > mid) return query_2(L, R, rs);
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
}
build(1, n, 1);
for (int i = 1; i <= m; ++ i) {
int tmp = read(), a = read(), b = read();
a++, b++;
if (tmp == 0) {
update_1(a, b, 0, 1);
} if (tmp == 1) {
update_1(a, b, 1, 1);
} else if (tmp == 2) {
update_2(a, b, 1);
} else if (tmp == 3) {
printf("%d\n", query_1(a, b, 1));
} else if (tmp == 4) {
printf("%d\n", query_2(a, b, 1).k);
}
}
return 0;
}