P8310 〈 TREEのOI 2022 Spring 〉Essential Operations Solution

Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$，有 $m$ 个操作分四种：

• $\mathrm{add}(l,r,k)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow a_i+k$.
• $\mathrm{mul}(l,r,k)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow a_i\times k$.
• $\mathrm{query}(l,r)$：求 $({\sum }_{i=l}^r{a}_i)\mathrm{mod}19260817$.
• $\mathrm{roll}()$：将序列回溯到上次 $\mathrm{roll}$ 操作前（若没有则为初始状态），并倒序执行这两次操作间的所有修改操作.

Limitations

$1\le n\le 5\times 10^5$
$1\le m\le 10^5$
$1\le a_i,x\le 10^3$
$0.5\text{s},45\text{MB}$

Solution

没有 $\mathrm{roll}$ 操作大家都会做吧.
就算需要回溯，也可用主席树完成，但是刁钻的空间限制让其不能胜任.
但可以发现，我们只需要回溯到上次 $\mathrm{roll}$ 操作前，因此我们只需维护上次 $\mathrm{roll}$ 操作前的数组.
但只开一棵线段树无法快速回溯，考虑再开一棵.
前 $3$ 个操作依旧用第一棵树完成，$\mathrm{roll}$ 时将两棵树交换，并倒序执行修改.
容易发现，此时的另一棵树恰好是 $\mathrm{roll}$ 前的状态.
由于每个操作最多被执行两次，时间复杂度仍为 $O(m\log n)$.

需要注意几点：

• 线段树 Node 上不要存 $l,r$，建议使用两倍空间写法.
• 不能开 long long，乘法时强转即可.
• 倒序时只用执行修改.
• 两棵树都要 build.

Code

$3.44\text{KB},3.47\text{s},26.83\text{MB}\text{(in total, C++20 with O2)}$
由于偷懒，在线段树中我把 $\mathrm{add}$ 和 $\mathrm{mul}$ 写到了一起.

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

constexpr int mod = 19260817;
inline int add(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
inline int mul(int x, int y) { return 1LL * x * y % mod; }
inline int ls(int u) { return 2 * u + 1; }
inline int rs(int u) { return 2 * u + 2; }

struct SegTree {
	struct Node {
		int sum, mul, add;
	};
	vector<Node> tr;
	inline SegTree() {}
	inline SegTree(const vector<int>& a) {
		const int n = a.size();
		tr.resize(n << 1);      // 2x memory
		build(0, 0, n - 1, a);
	}
	
	inline void pushup(int u, int mid) {
		tr[u].sum = add(tr[ls(mid)].sum, tr[rs(mid)].sum);
	}
	
	inline void apply(int u, int tag_mul, int tag_add, int len) {
		if (tag_mul != 1) {
			tr[u].sum = mul(tr[u].sum, tag_mul);
			tr[u].mul = mul(tr[u].mul, tag_mul);
			tr[u].add = mul(tr[u].add, tag_mul);
		}
		if (tag_add != 0) {
			tr[u].sum = add(tr[u].sum, mul(tag_add, len));
			tr[u].add = add(tr[u].add, tag_add);
		}
	}
	
	inline void pushdown(int u, int l, int mid, int r) {
		apply(ls(mid), tr[u].mul, tr[u].add, mid - l + 1);
		apply(rs(mid), tr[u].mul, tr[u].add, r - mid);
		tr[u].mul = 1, tr[u].add = 0;
	}
	
	inline void build(int u, int l, int r, const vector<int>& a) {
		tr[u].mul = 1, tr[u].add = 0;
		if (l == r) return (void)(tr[u].sum = a[l]);
		const int mid = (l + r) >> 1;
		build(ls(mid), l, mid, a), build(rs(mid), mid + 1, r, a);
		pushup(u, mid);
	}
	
	// Preform `a_i = a_i * mul + add` for each i in range [l, r].
	inline void update(int u, int l, int r, int L, int R, int mul, int add) {
		if (L <= l && r <= R) return apply(u, mul, add, r - l + 1);
		if (l > R || r < L) return;
		const int mid = (l + r) >> 1;
		pushdown(u, l, mid, r);
		update(ls(mid), l, mid, L, R, mul, add);
		update(rs(mid), mid + 1, r, L, R, mul, add);
		pushup(u, mid);
	}
	
	inline int query(int u, int l, int r, int L, int R) {
		if (L <= l && r <= R) return tr[u].sum;
		if (l > R || r < L) return 0;
		const int mid = (l + r) >> 1;
		pushdown(u, l, mid, r);
		return add(query(ls(mid), l, mid, L, R), query(rs(mid), mid + 1, r, L, R));
	}
};

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]);
	array<SegTree, 2> sgt{SegTree(a), SegTree(a)};
	
	auto range_add = [&](int now, int l, int r, int x) {
		sgt[now].update(0, 0, n - 1, l, r, 1, x);
	};
	auto range_mul = [&](int now, int l, int r, int x) {
		sgt[now].update(0, 0, n - 1, l, r, x, 0);
	};
	auto range_sum = [&](int now, int l, int r) {
		return sgt[now].query(0, 0, n - 1, l, r);
	};
	
	vector<int> op(m), L(m), R(m), X(m);
	for (int i = 0, now = 0; i < m; i++) {
		scanf("%d", &op[i]);
		if (op[i] == 4) {
			now ^= 1;
			for (int j = i - 1; j >= 0; j--) {
				if (op[j] == 4) break;
				else if (op[j] == 3) continue;
				else if (op[j] == 1) range_add(now, L[j], R[j], X[j]);
				else range_mul(now, L[j], R[j], X[j]);
			}
		}
		else {
			scanf("%d %d", &L[i], &R[i]), L[i]--, R[i]--;
			if (op[i] == 3) printf("%d\n", range_sum(now, L[i], R[i]));
			else {
				scanf("%d", &X[i]);
				if (op[i] == 1) range_add(now, L[i], R[i], X[i]);
				else range_mul(now, L[i], R[i], X[i]);
			}
		}
	}
	
	return 0;
}