随机跳的。
树上维护序列,显然树剖。维护异或,显然 01trie
。
01trie
维护区间异或,显然可持久化一下。
看到时限很大,显然可以双 log
。
于是跑一边树剖,再根据 id
暴力建一个 可持久化01trie
,单操 \(\mathrm{O(\log n \log w)}\)
(当然可以树上差分优成 \(\mathrm{O(\log w)}\),但是不想写了。)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )
#define dop(i, a, b) for (int i = (a); i > (b); i -- )
using namespace std;
using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
int read() {
int f = 1, s = 0; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48);
return s * f;
}
const int N = 100010, M = N << 1;
const long long INF = 1 << 30;
int h[N], e[M], ne[M], idx;
int n, m, w[N], nw[N], top[N];
int son[N], sz[N], id[N], cnt;
int fa[N], dep[N];
struct node {
node *s[2]; int maxid;
node() { s[0] = s[1] = NULL; maxid = 0; }
}*root[N], pool[N << 5], *tail; // 开个内存池会快很多诶
void add(int a, int b) {
e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}
// ------------ tree cut ----------------
void dfs1(int u, int father, int depth) {
dep[u] = depth, fa[u] = father, sz[u] = 1;
for (int i = h[u]; i; i = ne[i]) {
int j = e[i];
if (j == father) continue;
dfs1(j, u, depth + 1);
sz[u] += sz[j];
if (sz[son[u]] < sz[j]) son[u] = j;
}
}
void dfs2(int u, int t) {
top[u] = t, id[u] = ++ cnt, nw[cnt] = w[u];
if (son[u]) dfs2(son[u], t);
for (int i = h[u]; i; i = ne[i]) {
int j = e[i];
if (j == fa[u] || j == son[u]) continue;
dfs2(j, j);
}
}
// ------------- 01trie ---------------
void build() {
tail = pool;
node *u = root[0] = new(tail ++ ) node();
dep(i, 30, 0) u -> s[0] = new(tail ++ ) node(), u = u -> s[0];
}
void insert(int x) {
node *u = root[x] = new(tail ++ ) node(), *p = root[x - 1];
int v = nw[x];
dep(i, 30, 0) {
if (p) *u = *p;
u -> maxid = max(u -> maxid, x);
int t = (v >> i) & 1; u -> s[t] = new(tail ++ ) node();
u = u -> s[t]; p = p ? p -> s[t] : NULL;
}
u -> maxid = max(u -> maxid, x);
}
LL query(node *u, int x, int lim) {
dep(i, 30, 0) {
int t = (x >> i) & 1;
if (u -> s[t ^ 1] && u -> s[t ^ 1] -> maxid >= lim) u = u -> s[t ^ 1];
else u = u -> s[t];
}
return (LL)x ^ nw[u -> maxid];
}
LL query(int u, int v, int z) {
LL res = -INF;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
res = max(res, query(root[id[u]], z, id[top[u]]));
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
res = max(res, query(root[id[u]], z, id[v]));
return res;
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; i ++ )
w[i] = read();
for (int i = 1, a, b; i < n; i ++ ) {
a = read(), b = read();
add(a, b), add(b, a);
}
dfs1(1, -1, 1), dfs2(1, 1); build();
for (int i = 1; i <= n; i ++ )
insert(i);
while (m -- ) {
int op = read(), x = read(), y, z;
if (op == 1) {
z = read();
printf("%lld\n", query(root[id[x] + sz[x] - 1], z, id[x]));
}
else {
y = read(), z = read();
printf("%lld\n", query(x, y, z));
}
}
return 0;
}
标签:ch,maxid,int,Luogu,top,dep,异或,res,TJOI2018
From: https://www.cnblogs.com/LcyRegister/p/17037256.html