P2572 [SCOI2010] 序列操作 Solution

Description

给定 $01$ 序列 $a=(a_1,a_2,\cdots ,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;
}