全局平衡 WBLT
Yansuan_HCl
·
·
题解
没有子树和，事全局平衡二叉树很好的练习题。
首先可以维护一个函数 f_{a,o,x}(n)=((n\ \text{and}\ a)\ \text{or}\ o)\ \text{xor}\ x。可以知道这是支持复合的。所以其具有结合律，上线段树维护。
为了摊平线段树的 $\log$，可以预处理每个点的轻子树大小 $sz(u)-sz(\text{hson}(u))$。对每条重链建立线段树。线段树处理区间 $[l,r]$ 时，选取 $\text{mid}$ 为 $[l,r]$ 中轻子树大小前缀和的带权中点。
这样，树剖每跳一次，在线段树上的深度也相应减小。每次跳轻边，当次查询在线段树上的深度一定已经跳到了 $O(1)$。其实，等价于把全局平衡二叉树的二叉树换成 WBLT. 因此复杂度为 $O(n \log n)$。优势是 Leafy 且比较好写。
代码（丑见谅）：
```cpp
#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline)) static
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
typedef unsigned long long ll;
template <class T> using BS = basic_string<T>;
template <class T> void rd(T& s) {
int c = getchar(); T f = 1; s = 0;
while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); }
while (isdigit(c)) { s = s * 10 + (c ^ 48); c = getchar(); }
s *= f;
}
template <class T, class... Y> void rd(T& x, Y&... y) { rd(x), rd(y...); }
#define meow(...) fprintf(stderr, __VA_ARGS__)
const int N = 100005;
const ll INF = 0xFFFFFFFFFFFFFFFF;
int n, Q, K;
BS<int> g[N];
int dep[N], fa[N], siz[N], hson[N];
void df1(int u, int f) {
dep[u] = dep[f] + 1; fa[u] = f; siz[u] = 1;
for (int v : g[u]) if (v != f) {
df1(v, u);
siz[u] += siz[v];
if (siz[v] > siz[hson[u]])
hson[u] = v;
}
}
int top[N], lz[N], len[N], dfn[N];
void df2(int u, int f, int t) {
static int pt; dfn[u] = ++pt; top[u] = t; len[u] = 1;
if (hson[u]) df2(hson[u], u, t), len[u] = len[hson[u]] + 1;
lz[dfn[u]] = siz[u] - siz[hson[u]];
for (int v : g[u]) if (v != f && v != hson[u])
df2(v, u, v);
}
struct T {
ll a, o, x;
T() : a(INF), o(0), x(0) {}
T(int op, ll v) : a(INF), o(0), x(0) {
if (op == 1) a = v;
else if (op == 2) o = v;
else x = v;
}
} in[N];
T operator + (T l, T r) {
l.a &= r.a; l.o &= r.a; l.x &= r.a;
l.o |= r.o; l.x &= ~r.o;
l.x ^= r.x;
return l;
}
struct ST {
struct Node {
int ls, rs, mid;
T up, dn;
}; vector<Node> tr;
int L, R;
int build(int l, int r) {
assert(l <= r);
int p = tr.size(), ls, rs, mid; T up, dn; tr.push_back(Node());
if (l == r) { tr[p].up = tr[p].dn = in[l]; return p; }
int w = 0, h = 0; U (i, l, r) w += lz[i];
for (int i = l; h += lz[i], i <= r; ++i)
if (h * 2 >= w) {
mid = i;
break;
}
if (mid == r) --mid;
assert(mid >= l && mid < r);
ls = build(l, mid); rs = build(mid + 1, r);
up = tr[rs].up + tr[ls].up;
dn = tr[ls].dn + tr[rs].dn;
tr[p] = {ls, rs, mid, up, dn};
return p;
}
void modify(int x, T &v, int p, int l, int r) {
auto &[ls, rs, mid, up, dn] = tr[p];
if (l == r) { up = dn = v; return; }
if (x <= mid) modify(x, v, ls, l, mid);
else modify(x, v, rs, mid + 1, r);
up = tr[rs].up + tr[ls].up;
dn = tr[ls].dn + tr[rs].dn;
} void modify(int x, T &v) { modify(x, v, 0, L, R); }
T v;
void qU(int b, int e, int p, int l, int r) {
auto &[ls, rs, mid, up, dn] = tr[p];
if (b <= l && e >= r) { v = v + up; return; }
if (e > mid) qU(b, e, rs, mid + 1, r);
if (b <= mid) qU(b, e, ls, l, mid);
} T qU(int b, int e) { v = T(); qU(b, e, 0, L, R); return v; }
void qD(int b, int e, int p, int l, int r) {
auto &[ls, rs, mid, up, dn] = tr[p];
if (b <= l && e >= r) { v = v + dn; return; }
if (b <= mid) qD(b, e, ls, l, mid);
if (e > mid) qD(b, e, rs, mid + 1, r);
} T qD(int b, int e) { v = T(); qD(b, e, 0, L, R); return v; }
} tr[N];
T query(int u, int v) {
T a, b, r;
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) {
a = a + tr[top[u]].qU(dfn[top[u]], dfn[u]);
u = fa[top[u]];
} else {
b = tr[top[v]].qD(dfn[top[v]], dfn[v]) + b;
v = fa[top[v]];
}
}
if (dep[u] < dep[v])
r = tr[top[u]].qD(dfn[u], dfn[v]);
else
r = tr[top[u]].qU(dfn[v], dfn[u]);
return a + r + b;
}
ll greedy(T &t, ll m) {
ll v = 0, w = 0;
D (i, K - 1, 0) {
#define B(s) (((s) >> (i)) & 1)
ll d = (B(t.a) | B(t.o)) ^ B(t.x),
e = B(t.o) ^ B(t.x);
if (e) {
w |= 1ull << i;
} else if (d && (v | (1ull << i)) <= m) {
w |= 1ull << i; v |= 1ull << i;
}
}
return w;
}
int main() {
rd(n, Q, K);
int io[N]; ll iv[N]; U (i, 1, n) rd(io[i], iv[i]);
U (i, 2, n) { int u, v; rd(u, v); g[u] += v; g[v] += u; }
df1(1, 1);
df2(1, 1, 1);
U (i, 1, n) in[dfn[i]] = T(io[i], iv[i]);
U (i, 1, n) if (i == top[i]) {
tr[i].L = dfn[i], tr[i].R = dfn[i] + len[i] - 1;
tr[i].tr.reserve((tr[i].R - tr[i].L) * 2 + 5);
tr[i].build(tr[i].L, tr[i].R);
}
while (Q--) {
ll op, x, y, z; rd(op, x, y, z);
if (op == 1) {
T t = query(x, y);
ll ans = greedy(t, z);
printf("%llu\n", ans);
} else {
T v(y, z);
tr[top[x]].modify(dfn[x], v);
}
}
}
```
~~在本题中由于[常数较大](https://www.luogu.com.cn/record/103851897)跑不过[树剖](https://www.luogu.com.cn/record/103850937)。并且因为过大的常数，这种方法不能通过 DDP 加强版。~~