【NOI2019模拟2019.6.20】ichi(kruskal重构树+KD-tree)

Description:

1<=n<=1e5

题解：

首先在子树里就是dfs序的一段区间。

那么路径最小值>=d的点呢？

很容易想到把点分树建出来，然后再上面×××

如果套上这个东西的话就变成了$O(lo{g}^3)$，还不说空间有多大。

这个其实就是kruskal重构树的事，模拟时sb了，没想到kruskal重构树可以套到这个上面。

满足路径最小值>=d的点同样在kruskal重构树的一个子树里，也用dfs序搞搞。

那么就是个三维偏序问题，考虑到这题卡空间，最好写的显然是KD-tree。

Code：

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
#define ul unsigned long long
using namespace std;const int N = 1e5 + 5;int n, m, ty, x, y, z, op;
ll a[N], la;struct edge {int fi[N * 2], nt[N * 2], to[N * 2], tot;void link(int x, int y) {nt[++ tot] = fi[x], to[tot] = y, fi[x] = tot;}int fa[N * 2], p[N * 2], q[N * 2], tp;void dg(int x) {p[x] = ++ tp;for(int i = fi[x]; i; i = nt[i]) if(to[i] != fa[x])fa[to[i]] = x, dg(to[i]);q[x] = tp;}
} e1, e2;struct bb {int x, y, z;
} b[N];void init() {scanf("%d %d %d", &n, &m, &ty);fo(i, 1, n) scanf("%lld", &a[i]);fo(i, 1, n - 1) {scanf("%d %d %d", &x, &y, &z);e1.link(x, y); e1.link(y, x);b[i].x = x; b[i].y = y; b[i].z = z;}e1.dg(1);
}int cmp(bb a, bb b) { return a.z > b.z;}int f[N * 2], tf;
int F(int x) { return f[x] == x ? x : (f[x] = F(f[x]));}int fa[18][N * 2], fv[18][N * 2];void build_kruskal_tree() {sort(b + 1, b + n, cmp);fo(i, 1, 2 * n) f[i] = i;tf = n;fo(i, 1, n - 1) {int x = F(b[i].x), y = F(b[i].y); z = b[i].z;tf ++; f[x] = tf; f[y] = tf;fa[0][x] = tf; fa[0][y] = tf;fv[0][x] = z; fv[0][y] = z;e2.link(tf, x); e2.link(tf, y);}e2.dg(tf);fo(j, 1, 17) fo(i, 1, tf) {fa[j][i] = fa[j - 1][fa[j - 1][i]];fv[j][i] = fv[j - 1][fa[j - 1][i]];}
}int jump(int x, int y) {fd(i, 17, 0) if(fa[i][x] && fv[i][x] >= y)x = fa[i][x];return x;
}struct P {int a[2], i;
} c[N];
int o, tt, rt, tc[N];
int cc(P a, P b) { return a.a[o] < b.a[o];}
struct tree {int l, r;int mi[2], mx[2], a[2];ll lz, s;
} t[N];
#define i0 t[i].l
#define i1 t[i].r
void cmin(int &x, int y) { x > y ? x = y : 0;}
void cmax(int &x, int y) { x < y ? x = y : 0;}
void merge(tree &a, tree b) {fo(j, 0, 1) cmin(a.mi[j], b.mi[j]), cmax(a.mx[j], b.mx[j]);
}
void bt(int &i, int x, int y) {i = ++ tt;int m = x + y >> 1;nth_element(c + x, c + m, c + y + 1, cc);fo(j, 0, 1) t[i].mi[j] = t[i].mx[j] = t[i].a[j] = c[m].a[j];o = !o;if(x < m) bt(i0, x, m - 1), merge(t[i], t[i0]);if(m < y) bt(i1, m + 1, y), merge(t[i], t[i1]);o = !o;
}
void build_kd_tree() {fo(i, 1, n) c[i].a[0] = e1.p[i], c[i].a[1] = e2.p[i], c[i].i = i;bt(rt, 1, n);fo(i, 1, n) tc[c[i].i] = i;
}
void ad(int i, int x) {t[i].lz += x, t[i].s += x;
}
void down(int i) {if(t[i].lz) ad(i0, t[i].lz), ad(i1, t[i].lz), t[i].lz = 0;
}
int pl[2], pr[2], pw; ll px;
void add(int i, int x, int y) {fo(j, 0, 1) if(t[i].mx[j] < pl[j] || t[i].mi[j] > pr[j]) return;int ky = 1; fo(j, 0, 1) if(t[i].mi[j] < pl[j] || t[i].mx[j] > pr[j]) ky = 0;if(ky) { ad(i, px); return;}ky = 1; fo(j, 0, 1) if(t[i].a[j] < pl[j] || t[i].a[j] > pr[j]) ky = 0;if(ky) t[i].s += px;int m = x + y >> 1; down(i);if(x < m) add(i0, x, m - 1);if(m < y) add(i1, m + 1, y);
}
void ft(int i, int x, int y) {int m = x + y >> 1; down(i);if(m == pw) { px = t[i].s; return;}if(pw < m) ft(i0, x, m - 1); else ft(i1, m + 1, y);
}int main() {freopen("ichi.in", "r", stdin);freopen("ichi.out", "w", stdout);init();build_kruskal_tree();build_kd_tree();fo(i, 1, m) {scanf("%d", &op);if(op == 2) {scanf("%d %d %d", &z, &y, &x);if(ty) x = (x + la) % n + 1;int nx = jump(x, y);pl[0] = e1.p[x]; pr[0] = e1.q[x];pl[1] = e2.p[nx]; pr[1] = e2.q[nx];px = z;add(rt, 1, n);} else {scanf("%d", &x);if(ty) x = (x + la) % n + 1;px = 0; pw = tc[x];ft(1, 1, n);la = a[x] + px;pp("%lld\n", la);}}
}