https://www.lydsy.com/JudgeOnline/problem.php?id=5355
想在b站搜query on a tree系列不小心看到了这题
扑鼻而来的浓浓的OI风格的题面，6个操作，放在ACM界读完题就可以喷了(误
看到前三个操作...kdtree板子题，一维dfs序，一维dep，限制区间显然
后面三个操作...考虑树链剖分，这样点到根的路径就是几条不连续的链了
就把前面kdtree的一维dfs序换成树链剖分的方法得到的dfs序就行了
对于后面三个操作相当于把常写的树链剖分套线段树的线段树换成kdtree了
复杂度O(n*sqrt(n)*logn)，这样的话为什么后面三个操作不直接对树上路径进行操作呢...
写这个题...单纯为了一时爽...尤其是过了样例一发入魂的那种 feel...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + ;
int n, m, tot, head[N];
int fa[N], siz[N], dep[N];
int cnt, son[N], top[N], dfn[N], st[N], en[N];
int nowD, lx, ly, rx, ry, val;
ll ans;
struct edge{int to, next;}e[N];
struct node {
ll siz, val, sum, lazy1, lazy2;
int maxd[], mind[], d[];
node *c[];
node() {
val = sum = siz = , lazy1 = , lazy2 = -;
c[] = c[] = NULL;
}
void update();
void pushup();
void pushdown();
bool operator < (const node &a) const {
return d[nowD] < a.d[nowD];
}
}nodes[N];
node *null = new node;
node *root;
inline void node::update() {
if (c[] != null) {
if (c[] -> maxd[] > maxd[]) maxd[] = c[] -> maxd[];
if (c[] -> maxd[] > maxd[]) maxd[] = c[] -> maxd[];
if (c[] -> mind[] < mind[]) mind[] = c[] -> mind[];
if (c[] -> mind[] < mind[]) mind[] = c[] -> mind[];
}
if (c[] != null) {
if (c[] -> maxd[] > maxd[]) maxd[] = c[] -> maxd[];
if (c[] -> maxd[] > maxd[]) maxd[] = c[] -> maxd[];
if (c[] -> mind[] < mind[]) mind[] = c[] -> mind[];
if (c[] -> mind[] < mind[]) mind[] = c[] -> mind[];
}
siz = + c[] -> siz + c[] -> siz;
}
inline void node::pushup() {
sum = val + c[] -> sum + c[] -> sum;
}
inline void node::pushdown() {
if (lazy1 == && lazy2 == -) return;
if (lazy1 != ) {
if (c[] != null) {
c[] -> val += lazy1;
c[] -> sum += c[] -> siz * lazy1;
if (c[] -> lazy2 != -) c[] -> lazy2 += lazy1;
else c[] -> lazy1 += lazy1;
}
if (c[] != null) {
c[] -> val += lazy1;
c[] -> sum += c[] -> siz * lazy1;
if (c[] -> lazy2 != -) c[] -> lazy2 += lazy1;
else c[] -> lazy1 += lazy1;
}
lazy1 = ;
return;
}
if (lazy2 != -) {
if (c[] != null) {
c[] -> val = lazy2;
c[] -> sum = c[] -> siz * lazy2;
c[] -> lazy1 = ;
c[] -> lazy2 = lazy2;
}
if (c[] != null) {
c[] -> val = lazy2;
c[] -> sum = c[] -> siz * lazy2;
c[] -> lazy1 = ;
c[] -> lazy2 = lazy2;
}
lazy2 = -;
return;
}
}
inline void dfs1(int u) {
siz[u] = ;
for (int v, i = head[u]; i; i = e[i].next) {
v = e[i].to, fa[v] = u;
dep[v] = dep[u] + ;
dfs1(v), siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
inline void dfs2(int u, int tp) {
dfn[++ cnt] = u, st[u] = cnt, top[u] = tp;
if (son[u]) dfs2(son[u], tp);
for (int v, i = head[u]; i; i = e[i].next) {
v = e[i].to;
if (v != son[u]) dfs2(v, v);
}
en[u] = cnt;
}
inline node *build(int l, int r, int D) {
int mid = l + r >> ; nowD = D;
nth_element(nodes + l, nodes + mid, nodes + r);
node *res = &nodes[mid];
if (l != mid) res -> c[] = build(l, mid - , !D);
else res -> c[] = null;
if (r != mid) res -> c[] = build(mid + , r, !D);
else res -> c[] = null;
res -> update();
return res;
}
inline void query1(node *o) {
if (o == null) return;
if (lx > o -> maxd[] || ly > o -> maxd[] || rx < o -> mind[] || ry < o -> mind[])
return;
if (lx <= o -> mind[] && ly <= o -> mind[] && rx >= o -> maxd[]&& ry >= o -> maxd[]) {
ans += o -> sum;
return;
}
if (lx <= o -> d[] && rx >= o -> d[] && ly <= o -> d[] && ry >= o -> d[])
ans += o -> val;
o -> pushdown();
query1(o -> c[]), query1(o -> c[]);
}
inline void modify2(node *o) {
if (o == null) return;
if (lx > o -> maxd[] || ly > o -> maxd[] || rx < o -> mind[] || ry < o -> mind[])
return;
if (lx <= o -> mind[] && ly <= o -> mind[] && rx >= o -> maxd[] && ry >= o -> maxd[]) {
if (o -> lazy2 != -) o -> lazy2 += val;
else o -> lazy1 += val;
o -> sum += o -> siz * val;
o -> val += val;
return;
}
if (lx <= o -> d[] && rx >= o -> d[] && ly <= o -> d[] && ry >= o -> d[])
o -> val += val;
o -> pushdown();
modify2(o -> c[]), modify2(o -> c[]);
o -> pushup();
}
inline void modify3(node *o) {
if (o == null) return;
if (lx > o -> maxd[] || ly > o -> maxd[] || rx < o -> mind[] || ry < o -> mind[])
return;
if (lx <= o -> mind[] && ly <= o -> mind[] && rx >= o -> maxd[] && ry >= o -> maxd[]) {
o -> lazy1 = , o -> lazy2 = val;
o -> val = val, o -> sum = o -> siz * val;
return;
}
if (lx <= o -> d[] && rx >= o -> d[] && ly <= o -> d[] && ry >= o -> d[])
o -> val = val;
o -> pushdown();
modify3(o -> c[]), modify3(o -> c[]);
o -> pushup();
}
inline void ask4(node *o) {
if (o == null) return;
if (lx > o -> maxd[] || rx < o -> mind[]) return;
if (lx <= o -> mind[] && rx >= o -> maxd[]) {
ans += o -> sum;
return;
}
if (lx <= o -> d[] && rx >= o -> d[]) ans += o -> val;
o -> pushdown();
ask4(o -> c[]), ask4(o -> c[]);
}
inline void query4(int u) {
for (int fu = top[u]; fu != ; fu = top[u = fa[fu]])
lx = st[fu], rx = st[u], ask4(root);
lx = , rx = st[u], ask4(root);
}
inline void change5(node *o) {
if (o == null) return;
if (lx > o -> maxd[] || rx < o -> mind[])
return;
if (lx <= o -> mind[] && rx >= o -> maxd[]) {
if (o -> lazy2 != -) o -> lazy2 += val;
else o -> lazy1 += val;
o -> sum += o -> siz * val;
o -> val += val;
return;
}
if (lx <= o -> d[] && rx >= o -> d[])
o -> val += val;
o -> pushdown();
change5(o -> c[]), change5(o -> c[]);
o -> pushup();
}
inline void change6(node *o) {
if (o == null) return;
if (lx > o -> maxd[] || rx < o -> mind[]) return;
if (lx <= o -> mind[] && rx >= o -> maxd[]) {
o -> lazy1 = , o -> lazy2 = val;
o -> val = val, o -> sum = o -> siz * val;
return;
}
if (lx <= o -> d[] && rx >= o -> d[])
o -> val = val;
o -> pushdown();
change6(o -> c[]), change6(o -> c[]);
o -> pushup();
}
inline void modify5(int u) {
for (int fu = top[u]; fu != ; fu = top[u = fa[fu]])
lx = st[fu], rx = st[u], change5(root);
lx = , rx = st[u], change5(root);
}
inline void modify6(int u) {
for (int fu = top[u]; fu != ; fu = top[u = fa[fu]])
lx = st[fu], rx = st[u], change6(root);
lx = , rx = st[u], change6(root);
}
int main() {
ios::sync_with_stdio(false);
int testCase, op, u, l, r;
cin >> testCase >> n;
for (int j, i = ; i <= n; i ++)
cin >> j, e[++ tot] = {i, head[j]}, head[j] = tot;
dfs1(), dfs2(, );
for (int i = ; i <= n; i ++) {
nodes[i].d[] = nodes[i].maxd[] = nodes[i].mind[] = i;
nodes[i].d[] = nodes[i].maxd[] = nodes[i].mind[] = dep[dfn[i]];
nodes[i].val = nodes[i].sum = , nodes[i].lazy1 = , nodes[i].lazy2 = -;
}
root = build(, n, );
for (cin >> m; m --; ) {
cin >> op;
switch(op) {
case :
cin >> u >> l >> r;
lx = st[u], ly = dep[u] + l;
rx = en[u], ry = dep[u] + r;
ans = , query1(root), cout << ans << endl;
break;
case :
cin >> u >> l >> r >> val;
lx = st[u], ly = dep[u] + l;
rx = en[u], ry = dep[u] + r;
modify2(root);
break;
case :
cin >> u >> l >> r >> val;
lx = st[u], ly = dep[u] + l;
rx = en[u], ry = dep[u] + r;
modify3(root);
break;
case :
cin >> u, ans = ;
query4(u), cout << ans << endl;
break;
case :
cin >> u >> val;
modify5(u);
break;
case :
cin >> u >> val;
modify6(u);
break;
}
}
return ;
}代码细节:
kdtree指针跑的比数组快，在数组比较大的时候速度差距比较明显
kdtree的这个update写法是固定的，必须要判左右儿子非null才更新，(后续更新需要调用update的情况下)常数大概是一倍
update其实是可以和pushup合并为用同一个函数的，但考虑后续修改只修改值不修改每个点的二维坐标，所以我分开了(1s的差距)
change5和change6是可以被modify2和modify3替代的，当然这时候要在modify5和modify6里对ly和ry两个变量也做调整