Description

給定 $01$ 序列 $a=(a_1,a_2,?,a_n)$，并定義 $f(l,r)=[(\sum _{i=l}^r{a}_i)=r?l+1]$.
執行 $m$ 個操作，分五種：

• $\mathrm{reset}(l,r)$：對每個 $i\in [l,r]$ 執行 $a_i\leftarrow 0$.
• $\mathrm{set}(l,r)$：對每個 $i\in [l,r]$ 執行 $a_i\leftarrow 1$.
• $\mathrm{negate}(l,r)$：對每個 $i\in [l,r]$ 執行 $a_i\leftarrow 1?a_i$.
• $\mathrm{sum}(l,r)$：求 $\sum _{i=l}^r{a}_i$.
• $\mathrm{gss}(l,r)$：求 $\underset{[s,t]\in [l,r]}{\max }(t?s+1)\times f(s,t)$.

Limitations

$1\le n,m\le 10^5$
$1\le l\le r\le n$
$1\text{s},128\text{MB}$

Solution

線段樹做法.
節點上維護 $S=(\text{sum},\text{lsum},\text{rsum},\text{tsum},\text{len})$，用類似最大子段和的方法更新.
由于要取反，$0$ 和 $1$ 都分別需要一個 $S$（下記為 $S_0$ 和 $S_1$） .
然后需要標記 $T$，顯然 $T=(\text{cov},\text{rev})$（分別為賦值和取反標記）

• 考慮賦值，我們直接將 $S_{cov}$ 全部填上 $\text{len}$，$S_{1?cov}$ 全部清零（$\text{len}$ 要不變）
• 考慮翻轉，我們直接交換 $S_0$ 和 $S_1$.

然后需要考慮 $T+T$：

• 賦值可以直接打標記.
• 對于取反，當一個區間賦值后，取反就相當于賦值 $(1?\text{cov})$，那么我們可以將 $\text{cov}$ 取反（此時 $\text{rev}$ 沒用，要置為 $0$），否則，直接更新 $\text{rev}$.

有不少坑點：

• 下標從 $0$ 開始.
• 沒有被賦值的節點，$\text{cov}$ 要置為 $?1$ 表示沒有賦值.
• 更新 $S$ 時，左半區間滿了，$\text{lsum}$ 才能跨越中點，$\text{rsum}$ 同理.
• 先處理 $\text{cov}$ 再處理 $\text{rev}$.
• 打 $\text{rev}$ 標記時 ^= 1 不要寫成 = 1.

Code

$3.9\text{KB},0.45\text{s},11.63\text{MB}\text{(in?total,?C++20?with?O2)}$
建議封裝 $S$（見代碼中的 Data），會好寫不少.

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}namespace seg_tree {struct Data {int sum, lsum, rsum, tsum, len;inline Data() {}inline Data(int x) : sum(x), lsum(x), rsum(x), tsum(x), len(1) {}inline Data(int _sum, int _lsum, int _rsum, int _tsum, int _len): sum(_sum), lsum(_lsum), rsum(_rsum), tsum(_tsum), len(_len) {}};inline Data operator+(const Data& lhs, const Data& rhs) {const int _sum = lhs.sum + rhs.sum;const int _lsum = lhs.lsum + (lhs.sum == lhs.len) * rhs.lsum;const int _rsum = rhs.rsum + (rhs.sum == rhs.len) * lhs.rsum;const int _tsum = std::max({lhs.tsum, rhs.tsum, lhs.rsum + rhs.lsum});const int _len = lhs.len + rhs.len;return Data(_sum, _lsum, _rsum, _tsum, _len);}struct Node {int l, r;array<Data, 2> dat;int cov, rev;inline Data& operator[](int i) { return dat[i]; }inline Data operator[](int i) const { return dat[i]; }};inline int ls(int u) { return 2 * u + 1; }inline int rs(int u) { return 2 * u + 2; }struct SegTree {vector<Node> tr;inline SegTree() {}inline SegTree(const vector<int>& a) {const int n = a.size();tr.resize(n << 1);build(0, 0, n - 1, a);}inline void pushup(int u, int mid) {for (int i = 0; i < 2; i++) tr[u][i] = tr[ls(mid)][i] + tr[rs(mid)][i];}inline void apply(int u, int cov, int rev) {if (~cov) {const int len = tr[u][cov].len;tr[u][cov] = Data(len, len, len, len, len);tr[u][cov ^ 1] = Data(0, 0, 0, 0, len);tr[u].cov = cov;tr[u].rev = 0;return;}if (rev) {swap(tr[u][0], tr[u][1]);if (~tr[u].cov) tr[u].cov ^= 1;else tr[u].rev ^= 1;}}inline void pushdown(int u, int mid) {apply(ls(mid), tr[u].cov, tr[u].rev);apply(rs(mid), tr[u].cov, tr[u].rev);tr[u].cov = -1, tr[u].rev = 0;}void build(int u, int l, int r, const vector<int>& a) {tr[u].l = l, tr[u].r = r, tr[u].cov = -1;if (l == r) {for (int i = 0; i < 2; i++) tr[u][i] = Data(a[l] == i);return;}const int mid = (l + r) >> 1;build(ls(mid), l, mid, a);build(rs(mid), mid + 1, r, a);pushup(u, mid);}void update(int u, int l, int r, int cov, int rev) {if (l <= tr[u].l && tr[u].r <= r) return apply(u, cov, rev);const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(u, mid);if (l <= mid) update(ls(mid), l, r, cov, rev);if (r > mid) update(rs(mid), l, r, cov, rev);pushup(u, mid);}Data query(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u][1];const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(u, mid);if (r <= mid) return query(ls(mid), l, r);else if (l > mid) return query(rs(mid), l, r);else return query(ls(mid), l, r) + query(rs(mid), l, r);}inline void range_cover(int l, int r, int v) { update(0, l, r, v, 0); }inline void range_negate(int l, int r) { update(0, l, r, -1, 1); }inline int range_sum(int l, int r) { return query(0, l, r).sum; }inline int range_gss(int l, int r) { return query(0, l, r).tsum; }};
}
using seg_tree::SegTree;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m;scanf("%d %d", &n, &m);vector<int> a(n);for (int i = 0; i < n; i++) scanf("%d", &a[i]);SegTree sgt(a);for (int i = 0, op, l, r; i < m; i++) {scanf("%d %d %d", &op, &l, &r);if (op == 0) sgt.range_cover(l, r, 0);if (op == 1) sgt.range_cover(l, r, 1);if (op == 2) sgt.range_negate(l, r);if (op == 3) printf("%d\n", sgt.range_sum(l, r));if (op == 4) printf("%d\n", sgt.range_gss(l, r));}return 0;
}