今天我刷题了吗
搜索文档…
可持久化数组
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const double pi(acos(-1));
7
const int inf(0x3f3f3f3f);
8
const int mod(1e9 + 7);
9
const int maxn(1e6 + 10);
10
int cnt, a[maxn], root[maxn];
11
12
struct node {
13
int val, l, r;
14
} tree[maxn * 40];
15
16
template<typename T = int>
17
inline const T read()
18
{
19
T x = 0, f = 1;
20
char ch = getchar();
21
while (ch < '0' || ch > '9') {
22
if (ch == '-') f = -1;
23
ch = getchar();
24
}
25
while (ch >= '0' && ch <= '9') {
26
x = (x << 3) + (x << 1) + ch - '0';
27
ch = getchar();
28
}
29
return x * f;
30
}
31
32
template<typename T>
33
inline void write(T x, bool ln)
34
{
35
if (x < 0) {
36
putchar('-');
37
x = -x;
38
}
39
if (x > 9) write(x / 10, false);
40
putchar(x % 10 + '0');
41
if (ln) putchar(10);
42
}
43
44
void build(int l, int r, int& cur)
45
{
46
cur = ++cnt;
47
if (l == r) {
48
tree[cur].val = a[l];
49
return;
50
}
51
int mid = (l + r) >> 1;
52
build(l, mid, tree[cur].l);
53
build(mid + 1, r, tree[cur].r);
54
}
55
56
void update(int l, int r, int pos, int val, int pre, int& cur)
57
{
58
tree[cur = ++cnt] = tree[pre];
59
if (l == r) {
60
tree[cur].val = val;
61
return;
62
}
63
int mid = (l + r) >> 1;
64
if (pos <= mid) {
65
update(l, mid, pos, val, tree[pre].l, tree[cur].l);
66
} else {
67
update(mid + 1, r, pos, val, tree[pre].r, tree[cur].r);
68
}
69
}
70
71
int query(int l, int r, int pos, int cur)
72
{
73
if (l == r) {
74
return tree[cur].val;
75
}
76
int mid = (l + r) >> 1;
77
if (pos <= mid) {
78
return query(l, mid, pos, tree[cur].l);
79
}
80
return query(mid + 1, r, pos, tree[cur].r);
81
}
82
83
int main()
84
{
85
#ifdef ONLINE_JUDGE
86
#else
87
freopen("input.txt", "r", stdin);
88
#endif
89
ios::sync_with_stdio(false);
90
int n = read(), m = read();
91
for (int i = 1; i <= n; ++i) {
92
a[i] = read();
93
}
94
build(1, n, root[0]);
95
for (int i = 1; i <= m; ++i) {
96
int v = read(), op = read(), pos = read();
97
if (op == 1) {
98
int val = read();
99
update(1, n, pos, val, root[v], root[i]);
100
} else {
101
write(query(1, n, pos, root[i] = root[v]), true);
102
}
103
}
104
return 0;
105
}
Copied!
解法 2 pb_ds rope
被毒瘤数据卡了
1
#include <bits/stdc++.h>
2
#include <ext/rope>
3
4
using namespace std;
5
using namespace __gnu_cxx;
6
const int maxn(1e6 + 10);
7
rope<int> rp[maxn];
8
9
int main()
10
{
11
#ifndef ONLINE_JUDGE
12
freopen("input.txt", "r", stdin);
13
#endif
14
ios::sync_with_stdio(false);
15
int n, m;
16
cin >> n >> m;
17
rp[0].append(0);
18
for (int i = 1; i <= n; ++i) {
19
int x;
20
cin >> x;
21
rp[0].append(x);
22
}
23
for (int i = 1; i <= m; ++i) {
24
int v, op, pos, val;
25
cin >> v >> op >> pos;
26
rp[i] = rp[v];
27
if (op == 1) {
28
cin >> val;
29
rp[i].replace(pos, val);
30
} else {
31
cout << rp[i][pos] << endl;
32
}
33
}
34
return 0;
35
}
Copied!
最近更新 1yr ago
复制链接