5
D7lsu. 树题 - leiyuanze
source link: https://www.cnblogs.com/leiyuanze/p/17209233.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
SolutionSolution
又是一道考场想到做法写不出来的题
对于 ≥x≥x 的数全部 +1+1 的操作有个很优美的大材小用的想法，那就是分段函数
于是线段树倒着维护分段函数，为了快速统计，要记录线段树结点中每个点跳出本结点的值，vector 记下排序
于是区间可以拆成 loglog 段，每段二分 loglog 统计，注意到从后往前，拆开后分段函数不能合并，不然复杂度会错，但可以找到最大的值使得它扔进函数出来后 ≤k≤k，这需要在分段函数上二分更新，每个拆开后的区间更新一次
那么在树上就硬套个树剖，O(nlogn+qlog3n)O(nlogn+qlog3n)，恶心的是树上路径要维护向上和下的分段函数，记录的信息也要对应多维护，比较繁琐
但是 log3log3 过掉 2×1052×105 也是厉害的
正解当然得正确点 O(nlogn+qlog2n)O(nlogn+qlog2n)
考虑这个困难的操作，仍然是可以更巧妙地弄出最后有哪些数的
倒着加数 xx ，每次新加的数受之前加的数影响，可以发现新加的数就是当前自然数集合从小到大没有加入过的第 xx 个
那这样就可以简单的线段树上二分得到了
然后硬上树剖，考虑拆段后询问应该怎么处理
只有一个段时直接查询 ≤k≤k 的数有多少，记为 pp，那么下一个段就要查询 ≤k−p≤k−p 的数有多少了
仍然是要维护向上和向下信息的
代码当然是写了恶心的做法，毕竟考场上写了 4Kb4Kb 怎么可以弃掉
CodeCode
#include <iostream>#include <cstdio>#include <vector>#include <algorithm>#define eb emplace_backusing namespace std; template <typename Tp>void read(Tp &x) { x = 0; char ch = getchar(); int f = 0; for(; !isdigit(ch); f = (ch == '-' ? 1 : f), ch = getchar()); for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar()); if (f) x = ~x + 1;} const int N = 2e5 + 5, inf = 4e5;int n, m, a[N];vector<int> G[N]; int fa[N], dfn[N], sz[N], dfc, top[N], dep[N], son[N], ed[N], rev[N];void dfs1(int x) { sz[x] = 1, dep[x] = dep[fa[x]] + 1; for(auto v : G[x]) { if (v == fa[x]) continue; fa[v] = x, dfs1(v), sz[x] += sz[v], son[x] = (sz[son[x]] < sz[v] ? v : son[x]); }}void dfs2(int x, int t) { top[x] = t, ed[t] = x, dfn[x] = ++dfc, rev[dfc] = x; if (son[x]) dfs2(son[x], t); for(auto v : G[x]) { if (v == fa[x] || v == son[x]) continue; dfs2(v, v); }} struct node{int a, b;};typedef vector<node> Vec;vector<node> seg[2][N * 19];vector<int> vec[2][N * 19];int ls[N * 19], rs[N * 19], size, R[N], rt[N]; int MaxDefine(Vec &seg, int z){return (z == seg.size() - 1) ? inf : seg[z + 1].a - 1;} void Merge(Vec &c, Vec &a, Vec &b) { for(int i = 0, j = 0; i < a.size(); i++) { while (MaxDefine(b, j) < a[i].a + a[i].b) ++j; int now = a[i].a; while (j < b.size()) { c.eb(node{now, a[i].b + b[j].b}); if (MaxDefine(b, j) >= MaxDefine(a, i) + a[i].b) break; now = MaxDefine(b, j) + 1 - a[i].b, ++j; } }}void Merge(vector<int> &a, vector<int> &b) { int i = 0, j = 0, k = 0; vector<int> c(a.size() + b.size()); while (i < a.size() && j < b.size()) if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; while (i < a.size()) c[k++] = a[i++]; while (j < b.size()) c[k++] = b[j++]; swap(a, c);}void merge(vector<int> &a, vector<int> &b, Vec &c) { vector<int> d(b.size()); for(int i = 0, j = 0; i < b.size(); i++) { while (MaxDefine(c, j) < b[i]) ++j; d[i] = b[i] + c[j].b; } Merge(a, d);}void build(int t, int &p, int l, int r) { if (!p) p = ++size; if (l == r) { int now = a[rev[l + dfn[t] - 1]]; for(int j = 0; j < 2; j++) seg[j][p].eb(node{0, 0}), seg[j][p].eb(node{now, 1}), vec[j][p].eb(now); return; } int mid = l + r >> 1; build(t, ls[p], l, mid), build(t, rs[p], mid + 1, r); Merge(seg[0][p], seg[0][rs[p]], seg[0][ls[p]]), Merge(seg[1][p], seg[1][ls[p]], seg[1][rs[p]]); merge(vec[0][p] = vec[0][ls[p]], vec[0][rs[p]], seg[0][ls[p]]); merge(vec[1][p] = vec[1][rs[p]], vec[1][ls[p]], seg[1][rs[p]]);}void build(int t){R[t] = dfn[ed[t]] - dfn[t] + 1, build(t, rt[t], 1, R[t]);} void calc(Vec &seg, int &x) { int l = 0, r = seg.size() - 1, mid = l + r >> 1, z; for(; l <= r; mid = l + r >> 1) if (MaxDefine(seg, mid) >= x) z = mid, r = mid - 1; else l = mid + 1; x += seg[z].b;}int count(vector<int> &vec, int k) { int l = 0, r = vec.size() - 1, mid = l + r >> 1, z = -1; for(; l <= r; mid = l + r >> 1) if (vec[mid] <= k) z = mid, l = mid + 1; else r = mid - 1; return z + 1;}void update(int &Mx, Vec &seg) { int l = 0, r = seg.size() - 1, mid = l + r >> 1, z = 0; for(; l <= r; mid = l + r >> 1) if (seg[mid].a + seg[mid].b <= Mx) z = mid, l = mid + 1; else r = mid - 1; if (MaxDefine(seg, z) + seg[z].b <= Mx) Mx = MaxDefine(seg, z); else Mx -= seg[z].b;} int Query(int p, int fl, int l, int r, int x, int y, int &Mx) { if (!p || x > r || y < l || x > y) return 0; if (x <= l && r <= y){ int res = count(vec[fl][p], Mx); update(Mx, seg[fl][p]); return res; } int mid = l + r >> 1, res = 0; if (!fl) { if (x <= mid) res = Query(ls[p], fl, l, mid, x, y, Mx); if (y > mid) res += Query(rs[p], fl, mid + 1, r, x, y, Mx); } else { if (y > mid) res = Query(rs[p], fl, mid + 1, r, x, y, Mx); if (x <= mid) res += Query(ls[p], fl, l, mid, x, y, Mx); } return res;} int LCA(int x, int y) { while (top[x] ^ top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x, y); x = fa[top[x]]; } return (dep[x] < dep[y] ? x : y);}int solve(int u, int v, int k) { int w = LCA(u, v), res = 0, Mx = k; while (top[v] != top[w]) res += Query(rt[top[v]], 1, 1, R[top[v]], 1, dfn[v] - dfn[top[v]] + 1, Mx), v = fa[top[v]]; res += Query(rt[top[w]], 1, 1, R[top[w]], dfn[w] - dfn[top[w]] + 1, dfn[v] - dfn[top[w]] + 1, Mx); vector<int> d; while (top[u] != top[w]) d.eb(u), u = fa[top[u]]; if (dep[u] > dep[w]) res += Query(rt[top[w]], 0, 1, R[top[w]], dfn[w] - dfn[top[w]] + 2, dfn[u] - dfn[top[w]] + 1, Mx); for(int i = (int)d.size() - 1; ~i; i--) res += Query(rt[top[d[i]]], 0, 1, R[top[d[i]]], 1, dfn[d[i]] - dfn[top[d[i]]] + 1, Mx); return res;} int main() { freopen("tree.in", "r", stdin); freopen("tree.out", "w", stdout); int t; read(n), read(m), read(t); for(int i = 1; i <= n; i++) read(a[i]); for(int i = 1, u, v; i < n; i++) read(u), read(v), G[u].eb(v), G[v].eb(u); dfs1(1), dfs2(1, 1); for(int i = 1; i <= n; i++) if (top[i] == i) build(i); for(int i = 1, u, v, k, lst = 0; i <= m; i++) read(u), read(v), read(k), u ^= (lst * t), v ^= (lst * t), k ^= (lst * t), printf("%d\n", lst = solve(u, v, k));}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK