瞎扯
好久没写线段树了，找了一道线段树题
然后……
写了半个上午，调了半个上午+下午的半个小时……
没 谁 了
思路
这道题难就难在标记的下放，如果标记下放正确了，A这道题就不是问题了。（然而我不想讲下放= =）
如果没有 (4) 操作和 (2) 操作，需要维护的东西就很少了，只需要维护区间内 (1) 的个数。但是因为有 (4) 操作和 (2) 操作，所以我们还要记录几个信息：左端最长的 (0)、左端最长的 (1)、右端最长的 (0)、右端最长的 (1)、区间最长的连续的 (0)、区间最长的连续的 (1)（这里说的哪个端是从区间端点开始的），这样才能实现 (2) 操作和 (4) 操作。
下面看一下两区间合并时，信息如何合并：
- 左端最长连续的 (0) = 左区间左端最长连续的 (0) + {右区间左端最长连续的 (0)（如果左区间最长连续的 (0) 的个数等于左区间长度）}
- 左端最长连续的 (1) = 左区间左端最长连续的 (1) + {右区间左端最长连续的 (1)（如果左区间最长连续的 (1) 的个数等于左区间长度）}
- 右端最长连续的 (0) = 右区间右端最长连续的 (0) + {左区间右端最长连续的 (0)（如果右区间最长连续的 (0) 的个数等于右区间长度）}
- 右端最长连续的 (1) = 右区间右端最长连续的 (1) + {左区间右端最长连续的 (1)（如果右区间最长连续的 (1) 的个数等于右区间长度）}
- 区间内 (1) 的个数 = 左区间内 (1) 的个数 + 右区间内 (1) 的个数
- 区间最长连续的 (1) = (max()左区间最长连续 (1)，右区间最长连续 (1)， 左区间右端最长连续 (1) + 右区间左端最长连续 (1) ())
- 区间最长连续的 (0) = (max()左区间最长连续 (0)，右区间最长连续 (0)， 左区间右端最长连续 (0) + 右区间左端最长连续 (0) ())
然后要注意的就是标记的下传了，这里我们采用两个标记，一个赋值标记，一个取反标记，显然赋值标记的优先级是大于取反标记的（其实我不知道为啥，就凭感觉觉得这样是对的，评论区大佬可否解答？），所以我们先处理赋值标记，在处理赋值标记后，注意取反标记的贡献应该取消，在处理取反标记时，赋值标记也要取反……详细的实现可以看代码了……
代码
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson rt << 1
#define rson rt << 1 | 1
using namespace std;
const int A = 1e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, m, a[A];
struct node {
int sum1, l1, r1, max1;
void clear() { sum1 = 0, l1 = 0, r1 = 0, max1 = 0; }
};
struct tree {
int l, r, sum0, sum1, l0, l1, r0, r1, max1, max0, lazy1, lazy2;
} t[A << 2];
inline void pushup(int rt) {
t[rt].sum0 = t[lson].sum0 + t[rson].sum0;
t[rt].sum1 = t[lson].sum1 + t[rson].sum1;
t[rt].max0 = max(max(t[lson].max0, t[rson].max0), t[lson].r0 + t[rson].l0);
t[rt].max1 = max(max(t[lson].max1, t[rson].max1), t[lson].r1 + t[rson].l1);
t[rt].l0 = t[lson].l0 + t[rson].l0 * (t[lson].l0 == (t[lson].r - t[lson].l + 1));
t[rt].l1 = t[lson].l1 + t[rson].l1 * (t[lson].l1 == (t[lson].r - t[lson].l + 1));
t[rt].r0 = t[rson].r0 + t[lson].r0 * (t[rson].r0 == (t[rson].r - t[rson].l + 1));
t[rt].r1 = t[rson].r1 + t[lson].r1 * (t[rson].r1 == (t[rson].r - t[rson].l + 1));
return;
}
inline void tag(int rt) {
swap(t[rt].max0, t[rt].max1);
swap(t[rt].sum0, t[rt].sum1);
swap(t[rt].r0, t[rt].r1);
swap(t[rt].l0, t[rt].l1);
t[rt].lazy2 ^= 1, t[rt].lazy1 ^= 1;
return;
}
inline void change1(int rt) {
int len = t[rt].r - t[rt].l + 1;
t[rt].sum0 = 0, t[rt].max0 = 0, t[rt].l0 = 0, t[rt].r0 = 0;
t[rt].sum1 = len, t[rt].max1 = len, t[rt].l1 = len, t[rt].r1 = len;
t[rt].lazy1 = 1, t[rt].lazy2 = 0;
return;
}
inline void change0(int rt) {
int len = t[rt].r - t[rt].l + 1;
t[rt].sum1 = 0, t[rt].max1 = 0, t[rt].l1 = 0, t[rt].r1 = 0;
t[rt].sum0 = len, t[rt].max0 = len, t[rt].l0 = len, t[rt].r0 = len;
t[rt].lazy1 = 0, t[rt].lazy2 = 0;
return;
}
inline void pushdown(int rt) {
if (t[rt].lazy1 == 1) {
change1(lson), change1(rson);
t[rt].lazy1 = -1, t[rt].lazy2 = 0;
}
else if (t[rt].lazy1 == 0) {
change0(lson), change0(rson);
t[rt].lazy1 = -1, t[rt].lazy2 = 0;
}
if (t[rt].lazy2 == 1) {
tag(lson), tag(rson);
t[rt].lazy2 = 0, t[rt].lazy1 = -1;
}
}
void build(int rt, int l, int r) {
t[rt].l = l, t[rt].r = r, t[rt].lazy1 = -1;
if (l == r) {
int now = a[l];
if (now == 1) {
t[rt].l1 = 1, t[rt].r1 = 1;
t[rt].sum1 = 1, t[rt].max1 = 1;
}
else {
t[rt].l0 = 1, t[rt].r0 = 1;
t[rt].sum0 = 1, t[rt].max0 = 1;
}
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
pushup(rt);
}
void update(int rt, int l, int r, int who) {
if (l <= t[rt].l && t[rt].r <= r) {
pushdown(rt);
if (who) {
change1(rt);
} else {
change0(rt);
}
return;
}
pushdown(rt);
int mid = (t[rt].l + t[rt].r) >> 1;
if (l <= mid) {
update(lson, l, r, who);
}
if (r > mid) {
update(rson, l, r, who);
}
pushup(rt);
}
void Negate(int rt, int l, int r) {
if (l <= t[rt].l && t[rt].r <= r) {
pushdown(rt);
tag(rt);
return;
}
pushdown(rt);
int mid = (t[rt].l + t[rt].r) >> 1;
if (l <= mid) Negate(lson, l, r);
if (r > mid) Negate(rson, l, r);
pushup(rt);
}
node conseq(int rt, int l, int r) {
node now, ls, rs;
now.clear(), ls.clear(), rs.clear();
if (l <= t[rt].l && t[rt].r <= r) {
now.l1 = t[rt].l1, now.max1 = t[rt].max1, now.r1 = t[rt].r1, now.sum1 = t[rt].sum1;
return now;
}
pushdown(rt);
int mid = (t[rt].l + t[rt].r) >> 1;
if (l <= mid) ls = conseq(lson, l, r);
if (r > mid) rs = conseq(rson, l, r);
now.sum1 = ls.sum1 + rs.sum1;
now.max1 = max(max(ls.max1, rs.max1), ls.r1 + rs.l1);
now.l1 = ls.l1 + rs.l1 * (ls.l1 == (t[lson].r - t[lson].l + 1));
now.r1 = rs.r1 + ls.r1 * (rs.r1 == (t[rson].r - t[rson].l + 1));
return now;
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; i++) a[i] = read();
build(1, 1, n);
while (m--) {
int opt = read(), x = read() + 1, y = read() + 1;
if (opt == 1 || opt == 0) update(1, x, y, opt);
else if (opt == 2) Negate(1, x, y);
else if (opt == 3) cout << conseq(1, x, y).sum1 << '
';
else if (opt == 4) cout << conseq(1, x, y).max1 << '
';
}
return 0;
}