P7518题解

传送门：https://www.luogu.com.cn/problem/P7518

码量巨大的恶心题。

要判断 \([l,r]\) 内某个值是否出现过？以下标为一个维度，值域为另一个维度，二维数点。朴素的方法，我们点的信息储存出现次数，每次查询线段树差分即可。

对于本题，一个显然的贪心是：遇到当前需要收集的宝石肯定优先收集更优。考虑调整法证明：假设不收取当前宝石，收取后一个位置的宝石，收集进度相同，失去了当前位置与后一个位置之间的贡献，结果必定更劣。

于是这个转化为，从尾部路径向上跳，每次贪心找到最近的未收集的宝石。因为加上了最近的条件，朴素判断是否存在？（二分位置即可嘻嘻）。考虑更高效的实现，CTT有个经典题：https://www.luogu.com.cn/problem/P4137。 我们用点的信息储存当前值在序列出现的最大位置，我们不需要进行线段树差分，只需要在当前版本的线段树中查再与 \(l\) 比较大小即可。如果是序列上的问题可以离线线段树，因为在树上没办法离线，可持久化一下即可，这里比较的是与 \(l\) 的深度大小。

暴力往上跳显然是不可以接受的。参考倍增求lca的方法，我们可以用倍增优化跳链的过程。我们把值域线段树的节点拆成 \(\log_2c\) 个维护以当前节点为起点长度为 \(2^i\) 的链的终点可能处于的深度最大的点。

考虑具体查询，我们把 \(s\) 到 \(t\) 的路径拆成 \(s\) 到 \(lca(s,t)\) 和 \(lca(s,t)\) 到 \(t\) 两条链。

对于第一条链，从 \(s\) 开始，以第一颗宝石开始往上跳直到最后一个深度小于lca的宝石。对于第二条链，因为树上可持久化线段树的节点维护的是从当前节点到根的，我们没办法从上往下跳。因为收集的最后一颗宝石的位置具有单调性，二分收集的最后一颗宝石就能确定链的终点。注意，第二条链跳的过程是反的，终点的宝石是当前位置 \(-2^i+1\) 的宝石，拼链的时候额外维护当前节点向反方向的宝石跳到的位置即可。

这样做查询的复杂度是 \(O(q\log^3_2c)\)。二分一只 \(\log\)，倍增一只，可持久化线段树查询一只。复杂度难以接受。二分和倍增的 \(\log\) 显然无法消除。我们能不能通过预处理消掉查询的呢？我们发现如果保证在当前点收集宝石那么状态是稀疏的，每个位置不需要带上其他种类宝石的值域，我们可以预处理当前位置的宝石种类向前跳或向后跳的位置即可。我们分别对于两条链的起点先在可持久化线段树上跳到第一颗和最后一颗宝石出现的位置。然后再通过预处理得到的信息继续跳即可。这样只需要在可持久化线段树上查两次就可以了。

还有一些细节，比如倍增更新答案要临时储存最后统一更新，不如新增节点数会多 \(\log_2c\) 倍。实现非常麻烦。

总复杂度 \(O((n+q)\log^2_2c)\)。我的常数巨大无比加了很多神人优化，在沐浴更衣后祈祷在几毫秒内卡过去了。

#include <bits/stdc++.h>const int N = 2e5 + 1;using namespace std;int mp[N], a[N], n, m, c, fa[18][N], dep[N], pre[16][N], suf[16][N];inline int read() {char c;while ((c = getchar()) < '0' || c > '9');int res = c - '0';while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';return res;
}vector<int> e[N];int mx[N * 16 + 1][2][16], ls[N * 16 + 1], rs[N * 16 + 1];int root[N], tot;int Max[2][16];inline void update(int &p, int rt, int lp, int rp, int pos) {p = ++tot;if (lp == rp) {for (int i = 0; i <= 15; ++i)for (int j = 0; j <= 1; ++j)mx[p][j][i] = dep[mx[rt][j][i]] > dep[Max[j][i]] ? mx[rt][j][i] : Max[j][i];return;}int mid = (lp + rp) >> 1;if (pos <= mid) rs[p] = rs[rt], update(ls[p], ls[rt], lp, mid, pos);else ls[p] = ls[rt], update(rs[p], rs[rt], mid + 1, rp, pos);
}inline int query(int p, int lp, int rp, int pos, int f, int type) {while (lp != rp) {int mid = (lp + rp) >> 1;if (pos <= mid) p = ls[p], rp = mid;else p = rs[p], lp = mid + 1;}return mx[p][type][f];
}void dfs(int x, int f) {root[x] = root[f];dep[x] = dep[f] + 1, fa[0][x] = f;for (int i = 1; i <= 17; ++i) fa[i][x] = fa[i - 1][fa[i - 1][x]];if (!a[x]) {for (int y: e[x]) if (y != f) dfs(y, x);return;}memset(Max, 0, sizeof Max);Max[0][0] = Max[1][0] = x;int now = f;for (int i = 1; i <= 15; ++i) {if (a[x] + (1 << i - 1) > c || !now) break;Max[0][i] = query(root[now], 1, c, a[x] + (1 << i - 1), i - 1, 0);now = fa[0][Max[0][i]];}now = f;for (int i = 1; i <= 15; ++i) {if (a[x] - (1 << i - 1) <= 0 || !now) break;Max[1][i] = query(root[now], 1, c, a[x] - (1 << i - 1), i - 1, 1);now = fa[0][Max[1][i]];}update(root[x], root[x], 1, c, a[x]);for (int i = 0; i <= 15; ++i) {pre[i][x] = query(root[x], 1, c, a[x], i, 0);if (!pre[i][x]) break;}for (int i = 0; i <= 15; ++i) {suf[i][x] = query(root[x], 1, c, a[x], i, 1);if (!suf[i][x]) break;}for (int y: e[x]) if (y != f) dfs(y, x);
}int lca(int x, int y) {if (dep[y] < dep[x]) swap(x, y);for (int i = 17; ~i; --i) if (dep[fa[i][y]] >= dep[x]) y = fa[i][y];if (y == x) return x;for (int i = 17; ~i; --i) if (fa[i][x] != fa[i][y]) x = fa[i][x], y = fa[i][y];return fa[0][x];
}int main() {n = read(), m = read(), c = read();for (int i = 1; i <= c; ++i) {int x;cin >> x;mp[x] = i;}for (int i = 1; i <= n; ++i) cin >> a[i], a[i] = mp[a[i]];for (int i = 1; i < n; ++i) {int u = read(), v = read();e[u].push_back(v), e[v].push_back(u);}dfs(1, 0);int q = read();while (q--) {int s = read(), t = read();int k = lca(s, t);int now = 0, rt = query(root[s], 1, c, 1, 0, 0);for (int i = 15; ~i; --i) {if (!rt) break;if (dep[pre[i][rt]] >= dep[k]) now += 1 << i, rt = pre[1][pre[i][rt]];}int l = now, r = c;while (r >= l) {int mid = (l + r) >> 1;int tmid = mid;rt = query(root[t], 1, c, mid, 0, 0);++mid;for (int i = 15; ~i; --i) {if (!rt) break;if (dep[suf[i][rt]] >= dep[k]) mid -= 1 << i, rt = suf[1][suf[i][rt]];}if (mid <= now + 1) l = tmid + 1;else r = tmid - 1;}printf("%d\n", l - 1);}return 0;
}