【题解】洛谷P8310 〈TREEのOI·R1〉Essential Operations

题目传送门：〈TREEのOI·R1〉Essential Operations

10 pts

暴力模拟即可。

30 pts

暴力模拟即可。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct Oper {
	int op, l, r, x;
};
const int mod = 19260817;
int n, m, lst = -1, arr[500010], mem[500010], tmp[500010];
vector<Oper> oper;
inline void process(int op, int l, int r, int x) {
	x %= mod;
	if(op == 1)
		for(int i = l; i <= r; i++)   arr[i] = ((long long)arr[i] + x) % mod;
	if(op == 2)
		for(int i = l; i <= r; i++)   arr[i] = ((long long)arr[i] * x) % mod;
	if(op == 3) {
		int sum = 0;
		for(int i = l; i <= r; i++)   sum = ((long long)sum + arr[i]) % mod;
		cout << sum << endl;
	}
}
inline void print() {
	for(int i = 1; i <= n; i++)   cout << arr[i] << ' ';
	cout << endl;
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)   cin >> arr[i];
	copy(arr + 1, arr + 1 + n, mem + 1);
	for(int i = 1; i <= m; i++) {
		int op, l, r, x;
		cin >> op;
		if(op == 1 || op == 2)   cin >> l >> r >> x;
		if(op == 3)   cin >> l >> r;
		oper.push_back({op, l, r, x});
	}
	for(int i = 0; i < m; i++) {
		//cout << "Process:" << oper[i].op << ' ' << oper[i].l << ' ' << oper[i].r << ' ' << oper[i].x << endl;
		if(oper[i].op != 4)    process(oper[i].op, oper[i].l, oper[i].r, oper[i].x);
		else {
			copy(arr + 1, arr + 1 + n, tmp + 1);
			copy(mem + 1, mem + 1 + n, arr + 1);
			copy(tmp + 1, tmp + 1 + n, mem + 1);
			for(int j = i - 1; j >= lst + 1; j--)
				if(oper[j].op != 3) process(oper[j].op, oper[j].l, oper[j].r, oper[j].x);
			lst = i;
		}
		//print();
	}
	//system("pause");
	return 0;
}

50 pts

使用可持久化线段树优化暴力。

100 pts

注意这句话：

回溯到上一次4操作前（如果不存在上一次则回溯到初始状态），倒序执行上一次回溯后到回溯前的所有1操作和2操作

为什么是上一次4操作前？按照正常的逻辑不应该是上一次4操作后吗？

这句话就是一个突破口，我们可以离线执行，建立两棵线段树，一棵正序执行并输出结果，一棵从下一个4操作开始逆序执行所有操作。

每当遇到4操作，只需要交换一下两棵线段树，用原本倒序的线段树正序执行接下来的操作，即可 $O(1)$ 实现4操作。

#include <iostream>
#include <cstdio>
using namespace std;
const int p = 19260817;
int n, m, arr[500010];
namespace smt {
int tree[2][4000010], add[2][4000010], mul[2][4000010];
inline void pushup(int rt,int id) {
	tree[rt][id] = (tree[rt][id<<1] + tree[rt][id<<1|1]) % p;
}
inline void pushdown(int rt, int id, int l, int r) {
	int mid = l + r >> 1;
	tree[rt][id<<1] = ((long long)tree[rt][id<<1] * mul[rt][id] + (long long)add[rt][id] * (mid - l + 1) % p) % p;
	tree[rt][id<<1|1] = ((long long)tree[rt][id<<1|1] * mul[rt][id] + (long long)add[rt][id] * (r - mid) % p) % p;
	mul[rt][id<<1] = ((long long)mul[rt][id<<1] * mul[rt][id]) % p;
	mul[rt][id<<1|1] = ((long long)mul[rt][id<<1|1] * mul[rt][id]) % p;
	add[rt][id<<1] = ((long long)add[rt][id<<1] * mul[rt][id] + add[rt][id]) % p;
	add[rt][id<<1|1] = ((long long)add[rt][id<<1|1] * mul[rt][id] + add[rt][id]) % p;
	mul[rt][id] = 1, add[rt][id] = 0;
}
void build(int rt, int id, int l, int r) {
	mul[rt][id] = 1;
	if(l == r) {
		tree[rt][id] = arr[l] % p;
		return;
	}
	int mid = l + r >> 1;
	build(rt, id<<1, l, mid);
	build(rt, id<<1|1, mid + 1, r);
	pushup(rt, id);
}
void adjust1(int rt, int id, int x, int y, int k, int l, int r) {
	if(!id)	return;
	if(x <= l && r <= y) {
		add[rt][id] = (long long)(add[rt][id] + k) % p;
		tree[rt][id] = (tree[rt][id] + (long long)(r - l + 1) * k) % p;
		return;
	}
	pushdown(rt, id, l, r);
	int mid = l + r >> 1;
	if(x <= mid)  adjust1(rt, id<<1, x, y, k, l, mid);
	if(mid < y)   adjust1(rt, id<<1|1, x, y, k, mid + 1, r);
	pushup(rt, id);
}
void adjust2(int rt, int id, int x, int y, int k, int l, int r) {
	if(!id)	return;
	if(x <= l && r <= y) {
		tree[rt][id] = ((long long)tree[rt][id] * k) % p;
		mul[rt][id] = ((long long)mul[rt][id] * k) % p;
		add[rt][id] = ((long long)add[rt][id] * k) % p;
		return;
	}
	pushdown(rt, id, l, r);
	int mid = l + r >> 1;
	if(x <= mid)  adjust2(rt, id<<1, x, y, k, l, mid);
	if(mid < y)   adjust2(rt, id<<1|1, x, y, k, mid + 1, r);
	pushup(rt, id);
}
int query(int rt, int id, int x, int y, int l, int r) {
	if(!id)	return 0;
	if(x <= l && r <= y) return tree[rt][id] % p;
	pushdown(rt, id, l, r);
	int mid = l + r >> 1, res = 0;
	if(x <= mid)  res = query(rt, id<<1, x, y, l, mid) % p;
	if(mid < y)   res = (res + query(rt, id<<1|1, x, y, mid + 1, r)) % p;
	return res;
}
}
struct Oper {
	int op, l, r, x;
} oper[100010];
int op_4[100010], cnt, cur;
inline void process(int i, int rt, bool prt) {
	if(i <= 0)	return;
	Oper op = oper[i];
	if(op.op == 1)	smt::adjust1(rt, 1, op.l, op.r, op.x, 1, n);
	else if(op.op == 2)	smt::adjust2(rt, 1, op.l, op.r, op.x, 1, n);
	else if(op.op == 3 && prt)	cout << smt::query(rt, 1, op.l, op.r, 1, n) << endl;
}
inline void init() {
	smt::build(0, 1, 1, n);
	smt::build(1, 1, 1, n);
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)	cin >> arr[i];
	for(int i = 1; i <= m; i++) {
		cin >> oper[i].op;
		if(oper[i].op < 4)	cin >> oper[i].l >> oper[i].r;
		if(oper[i].op < 3)	cin >> oper[i].x;
		if(oper[i].op == 4)	op_4[++cnt] = i;
	}
	init();
	int cur_op_4 = 0;
	for(int i = 1; i <= m; i++) {
		int rev = op_4[cur_op_4] + op_4[cur_op_4 + 1] - i;
		if(oper[i].op == 4) {
			cur_op_4++;
			cur ^= 1;
		} else process(i, cur, true), process(rev, cur^1, false);
	}
	//system("pause");
	return 0;
}