不建议使用vector,建议使用new关键字动态分配内存
by scp020 @ 2023-12-09 17:47:31
不建议使用 new,建议使用 vector 动态分配内存
by Argvchs @ 2023-12-11 09:23:33
浅调了一下(4h),跳出来的AC Code,自认为是vector拷贝的问题
```cpp
#include <cstdio>
#include <vector>
const int maxn = 1e6 + 1;
struct Node {
int val = 0;
int ls = 0, rs = 0;
};
#define mid(l, r) (((r - l) >> 1) + l)
int n, m, a[maxn];
std::vector<Node> seg;
int asgin() { //here
seg.push_back(Node());
return seg.size() - 1;
}
int build(int l = 1, int r = n) {
int p = asgin();
if (l == r) {
seg[p].val = a[l];
} else {
int m = mid(l, r), ls, rs;
ls = build(l, m);
rs = build(m + 1, r);
seg[p] = {0, ls, rs};
}
return p;
}
int modify(int p, int x, int k, int l = 1, int r = n) {
int o = asgin();
if (l == r) {
seg[o].val = k;
} else {
seg[o] = seg[p];
int m = mid(l, r), ls, rs;
if (x <= m) ls = modify(seg[p].ls, x, k, l, m), seg[o].ls = ls;
else rs = modify(seg[p].rs, x, k, m + 1, r), seg[o].rs = rs;
}
return o;
}
int query(int p, int x, int l = 1, int r = n) {
if (l == r) return seg[p].val;
int m = mid(l, r);
if (x <= m) return query(seg[p].ls, x, l, m);
else return query(seg[p].rs, x, m + 1, r);
}
int root[maxn];
void Solve() {
scanf("%d%d", &n, &m);
for (int cur = 1; cur <= n; ++cur) {
scanf("%d", a + cur);
}
root[0] = build();
for (int cur = 1; cur <= m; ++cur) {
int ver, opt;
scanf("%d%d", &ver, &opt);
if (opt == 1) {
int pos, val;
scanf("%d%d", &pos, &val);
root[cur] = modify(root[ver], pos, val);
} else {
int pos;
scanf("%d", &pos);
printf("%d\n", query(root[ver], pos));
root[cur] = root[ver];
}
}
}
int main() {
Solve();
return 0;
}
```
by DAMDAM @ 2023-12-16 20:08:07