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;
}