https://www.luogu.org/record/show?rid=16026345
by iodwad @ 2019-02-02 19:49:24
emmm 把主席树动态开点删掉就过了。。。
并不清楚是为什么
请问各位
下面是改过的代码（删去动态开点）
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
const int MAXN = 8e4;
int n, m, t, tot, lg;
int a[MAXN | 1], p[MAXN | 1], father[24][MAXN | 1], depth[MAXN | 1], fset[MAXN | 1], size[MAXN | 1];
std::vector < int > e[MAXN | 1];
inline int read() {
register int x = 0;
register char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
int find(int x) {
return fset[x] == x ? x : fset[x] = find(fset[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
size[y] += size[x];
fset[x] = y;
}
namespace persistentSegmentTree {
struct Node {
int sumv;
Node *ch[2];
Node() : sumv(0) {
ch[0] = ch[1] = NULL;
}
} *root[MAXN | 1];
inline int sumv(Node *o) {
return o == NULL ? 0 : o -> sumv;
}
inline void pushup(Node *o) {
o -> sumv = sumv(o -> ch[0]) + sumv(o -> ch[1]);
}
/*
void insert(Node *lst, Node *&now, int l, int r, int pos) {
if(now == NULL) now = new Node;
if(l == r) {
now -> sumv = sumv(lst) + 1;
return;
}
int mid = (l + r) >> 1;
if(lst != NULL) {
if(pos <= mid) {
now -> ch[1] = lst -> ch[1];
insert(lst -> ch[0], now -> ch[0], l, mid, pos);
} else {
now -> ch[0] = lst -> ch[0];
insert(lst -> ch[1], now -> ch[1], mid + 1, r, pos);
}
} else {
if(pos <= mid) insert(NULL, now -> ch[0], l, mid, pos);
else insert(NULL, now -> ch[1], mid + 1, r, pos);
}
pushup(now);
}
int query(Node *x, Node *y, Node *lca, Node *fa, int l, int r, int k) {
if(l == r) return l;
int delta = sumv(x ? x -> ch[0] : x) + sumv(y ? y -> ch[0] : y) - sumv(lca ? lca -> ch[0] : lca) - sumv(fa ? fa -> ch[0] : fa);
int mid = (l + r) >> 1;
if(delta >= k) return query(x ? x -> ch[0] : x, y ? y -> ch[0] : y, lca ? lca -> ch[0] : lca, fa ? fa -> ch[0] : fa, l, mid, k);
return query(x ? x -> ch[1] : x, y ? y -> ch[1] : y, lca ? lca -> ch[1] : lca, fa ? fa -> ch[1] : fa, mid + 1, r, k - delta);
}
*/
void build(Node *&now, int l, int r) {
now = new Node;
if(l == r) return;
int mid = (l + r) >> 1;
build(now -> ch[0], l, mid);
build(now -> ch[1], mid + 1, r);
}
void insert(Node *lst, Node *&now, int l, int r, int pos) {
if(now == NULL) now = new Node;
if(l == r) {
now -> sumv = lst -> sumv + 1;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) {
now -> ch[1] = lst -> ch[1];
insert(lst -> ch[0], now -> ch[0], l, mid, pos);
} else {
now -> ch[0] = lst -> ch[0];
insert(lst -> ch[1], now -> ch[1], mid + 1, r, pos);
}
pushup(now);
}
int query(Node *x, Node *y, Node *lca, Node *fa, int l, int r, int k) {
if(l == r) return l;
int delta = x -> ch[0] -> sumv + y -> ch[0] -> sumv - lca -> ch[0] -> sumv - fa -> ch[0] -> sumv;
int mid = (l + r) >> 1;
if(delta >= k) return query(x -> ch[0], y -> ch[0], lca -> ch[0], fa -> ch[0], l, mid, k);
return query(x -> ch[1], y -> ch[1], lca -> ch[1], fa -> ch[1], mid + 1, r, k - delta);
}
}
using namespace persistentSegmentTree;
void dfs(int x, int fa) {
father[0][x] = fa;
depth[x] = depth[fa] + 1;
insert(root[fa], root[x], 1, tot, a[x]);
if(fa) merge(x, fa);
for(int i = 1; i <= lg; ++i) father[i][x] = father[i - 1][father[i - 1][x]];
for(std::vector < int >::iterator it = e[x].begin(); it != e[x].end(); ++it) {
int to = *it;
if(to == fa) continue;
dfs(to, x);
}
}
int LCA(int x, int y) {
if(depth[x] < depth[y]) std::swap(x, y);
for(int i = lg; ~i; --i) if(father[i][x] && depth[father[i][x]] >= depth[y]) x = father[i][x];
if(x == y) return x;
for(int i = lg; ~i; --i) {
if(father[i][x] && father[i][y] && father[i][x] != father[i][y]) {
x = father[i][x];
y = father[i][y];
}
}
return father[0][x];
}
int ask(int x, int y, int z) {
int lca = LCA(x, y);
return query(root[x], root[y], root[lca], root[father[0][lca]], 1, tot, z);
}
void dfsMerge(int x, int fa) {
father[0][x] = fa;
depth[x] = depth[fa] + 1;
insert(root[fa], root[x], 1, tot, a[x]);
for(int i = 1; i <= lg; ++i) father[i][x] = father[i - 1][father[i - 1][x]];
for(std::vector < int >::iterator it = e[x].begin(); it != e[x].end(); ++it) {
int to = *it;
if(to != fa) dfsMerge(to, x);
}
}
void doit(int x, int y) {
int fx = find(x), fy = find(y);
if(size[fx] > size[fy]) {
std::swap(x, y);
}
e[x].push_back(y);
e[y].push_back(x);
merge(x, y);
dfsMerge(x, y);
}
int main() {
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
read();
n = read();
m = read();
t = read();
for(int i = 0, l = 1; ; ++i, l <<= 1) {
if(l > n) {
lg = i - 1;
break;
}
}
for(int i = 1; i <= n; ++i) {
a[i] = p[i] = read();
fset[i] = i;
size[i] = 1;
}
std::sort(p + 1, p + 1 + n);
tot = std::unique(p + 1, p + 1 + n) - p - 1;
for(int i = 1; i <= n; ++i) a[i] = std::lower_bound(p + 1, p + 1 + tot, a[i]) - p;
// for(int i = 1; i <= n; ++i) printf("%d ", a[i]);
for(int i = 1; i <= m; ++i) {
int u = read(), v = read();
e[u].push_back(v);
e[v].push_back(u);
}
build(root[0], 1, tot);
for(int i = 1; i <= n; ++i) if(!depth[i]) dfs(i, 0);
int lastans = 0;
while(t--) {
char opt;
std::cin >> opt;
if(opt == 'Q') {
int x = read() ^ lastans, y = read() ^ lastans, z = read() ^ lastans;
lastans = p[ask(x, y, z)];
printf("%d\n", lastans);
} else {
int x = read() ^ lastans, y = read() ^ lastans;
doit(x, y);
}
}
return 0;
}
```
by iodwad @ 2019-02-02 20:08:17
找到问题了。。。是因为动态开点没有删去以前的信息
已经 AC
by iodwad @ 2019-02-02 20:27:31