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

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

10 pts

暴力模拟即可。

30 pts

暴力模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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)O(1) 实现4操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#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;
}

【题解】洛谷P8310 〈TREEのOI·R1〉Essential Operations
https://www.d0j1a1701.cc/p/477c80cd/
作者
d0j1a_1701
发布于
2022年2月24日
许可协议
CC-BY-SA