「NOIP2024」树上查询
给出一棵包含 n 个节点的树,以 1 为根。
定义 \mathrm{dep}_u 表示节点 u 的深度,定义 \mathrm{LCA}^{*}(l, r) 表示区间 [l, r] 中所有节点的最近公共祖先。
有 Q 次查询,每次查询给出三个整数 l, r, k,你需要求出
数据范围:1 \leq n, Q \leq 5 \times 10^5,1 \leq l \leq r \leq n,1 \leq k \leq r - l + 1。
时空限制:2s / 1024MiB。
Solution
膜拜 CLYZ 大神学弟 hhz,爆切此题。
对于 l < r 的区间 [l, r],有
证明:我们考虑证明至少有一个 l \leq i < r 对应的 \mathrm{LCA}(i, i + 1) 可以取到 \mathrm{LCA}^{*}(l, r)。将区间 [l, r] 中的所有点,按照 \mathrm{LCA}^{*}(l, r) 的子树划分进行染色,不难发现区间 [l, r] 中必定有相邻异色的点对 i, i + 1(否则整个区间只有一种颜色),此时 i, i + 1 来自 \mathrm{LCA}^{*}(l, r) 的不同子树,故有 \mathrm{LCA}(i, i + 1) = \mathrm{LCA}^{*}(l, r)。
首先特判掉 k = 1 的情况。对于 k > 1 的情况,我们先令 r, k 都减去 1,记 v_i = \mathrm{dep}_{\mathrm{LCA}(i, i + 1)},我们要求的即为
考虑对 v_i 建出笛卡尔树(小根堆),找出以 v_i 为最小值的极长区间 [x_i, y_i]。对于一个询问 l, r, k,只需要区间 [l, r] 与 [x_i, y_i] 的交集大小 \geq k,则对答案就有 v_i 的贡献。
(仔细思考可以发现,如果交集不包含 i 也没有关系,由笛卡尔树结构此时肯定会找到 \geq v_i 的答案)
现在就是要考虑如何处理交集关系?可以按照右端点的位置关系分类。
第一类:y_i > r
此时有:
第二类:y_i \leq r
此时有:
两类情况均可扫描线。第一类情况,将 r 从右扫到左;第二类情况,将 k 从大扫到小。
时间复杂度 \mathcal{O}(n \log n)。
#include <bits/stdc++.h>
#define debug(a) std::cout << #a << "=" << (a) << ' '
using s64 = long long;
using u64 = unsigned long long;
/* 取 min */
template <class T>
inline void chmin(T &x, const T &y) {
if (x > y) {
x = y;
}
}
/* 取 max */
template <class T>
inline void chmax(T &x, const T &y) {
if (x < y) {
x = y;
}
}
/* ----- ----- ----- 正文 ----- ----- ----- */
const int N = 500100;
int n, Q;
struct Graph {
std::vector< std::vector<int> > table;
void init(int _n) {
table.assign(_n + 1, {});
}
void add_edge(int u, int v) {
table[u].push_back(v);
}
} G;
int dep[N];
int anc[20][N];
void dfs_init(int u, int fu) {
dep[u] = dep[fu] + 1;
anc[0][u] = fu;
for (int i = 1; i <= 19; i ++) anc[i][u] = anc[i - 1][anc[i - 1][u]];
for (int v : G.table[u]) {
if (v == fu) continue;
dfs_init(v, u);
}
}
int lca(int x, int y) {
if (dep[x] > dep[y]) std::swap(x, y);
for (int i = 19; i >= 0; i --)
if (dep[x] <= dep[anc[i][y]]) y = anc[i][y];
if (x == y) return x;
for (int i = 19; i >= 0; i --)
if (anc[i][x] ^ anc[i][y]) x = anc[i][x], y = anc[i][y];
return anc[0][x];
}
int value[N];
namespace dkr {
int rt;
struct node {
int lc, rc;
int le, rg;
} t[N];
int top, stk[N];
void build() {
for (int i = 1; i < n; i ++) {
int k = top;
while (k && value[stk[k]] > value[i]) k --;
if (k) t[stk[k]].rc = i;
if (k < top) t[i].lc = stk[k + 1];
stk[top = k + 1] = i;
}
rt = stk[1];
}
void dfs_init(int u) {
t[u].le = t[u].rg = u;
if (t[u].lc) {
dfs_init(t[u].lc);
t[u].le = t[t[u].lc].le;
}
if (t[u].rc) {
dfs_init(t[u].rc);
t[u].rg = t[t[u].rc].rg;
}
}
}
namespace SGT {
struct node {
int max;
} t[N * 4];
void build(int p, int l, int r) {
if (l == r) {
t[p].max = dep[l];
return;
}
int mid = (l + r) >> 1;
build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
t[p].max = std::max(t[p * 2].max, t[p * 2 + 1].max);
}
void init(int p, int l, int r) {
t[p].max = 0;
if (l == r) return;
int mid = (l + r) >> 1;
init(p * 2, l, mid), init(p * 2 + 1, mid + 1, r);
}
void change(int p, int l, int r, int x, int y) {
chmax(t[p].max, y);
if (l == r) return;
int mid = (l + r) >> 1;
if (x <= mid) {
change(p * 2, l, mid, x, y);
} else {
change(p * 2 + 1, mid + 1, r, x, y);
}
}
int ask(int p, int l, int r, int s, int e) {
if (s <= l && r <= e) {
return t[p].max;
}
int mid = (l + r) >> 1;
if (s <= mid && mid < e) {
return std::max(ask(p * 2, l, mid, s, e), ask(p * 2 + 1, mid + 1, r, s, e));
}
if (s <= mid) {
return ask(p * 2, l, mid, s, e);
} else {
return ask(p * 2 + 1, mid + 1, r, s, e);
}
}
}
std::vector< std::tuple<int, int, int, int> > seq;
int ans[N];
void scan1() {
std::vector< std::vector< std::tuple<int, int> > > qry(n + 1);
std::vector< std::vector< std::tuple<int, int> > > scan(n + 1);
for (auto [l, r, k, id] : seq) {
qry[r].push_back({r - k + 1, id});
}
for (int i = 1; i < n; i ++) {
int x = dkr::t[i].le, y = dkr::t[i].rg, v = value[i];
scan[y].push_back({x, v});
}
SGT::init(1, 1, n);
for (int i = n; i >= 1; i --) {
if (i < n) {
for (auto [x, v] : scan[i + 1]) {
SGT::change(1, 1, n, x, v);
}
}
for (auto [l, id] : qry[i]) {
chmax(ans[id], SGT::ask(1, 1, n, 1, l));
}
}
}
void scan2() {
std::vector< std::vector< std::tuple<int, int, int> > > qry(n + 1);
std::vector< std::vector< std::tuple<int, int> > > scan(n + 1);
for (auto [l, r, k, id] : seq) {
qry[k].push_back({l + k - 1, r, id});
}
for (int i = 1; i < n; i ++) {
int x = dkr::t[i].le, y = dkr::t[i].rg, v = value[i];
scan[y - x + 1].push_back({y, v});
}
SGT::init(1, 1, n);
for (int i = n; i >= 1; i --) {
for (auto [y, v] : scan[i]) {
SGT::change(1, 1, n, y, v);
}
for (auto [l, r, id] : qry[i]) {
chmax(ans[id], SGT::ask(1, 1, n, l, r));
}
}
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cin >> n;
G.init(n);
for (int i = 1; i < n; i ++) {
int x, y;
std::cin >> x >> y;
G.add_edge(x, y), G.add_edge(y, x);
}
/* 预处理 le[], rg[], value[] */
dfs_init(1, 0);
for (int i = 1; i < n; i ++) {
value[i] = dep[lca(i, i + 1)];
}
dkr::build();
dkr::dfs_init(dkr::rt);
// for (int i = 1; i < n; i ++) {
// int x = dkr::t[i].le, y = dkr::t[i].rg, v = value[i];
// std::cout << ' ' << x << ' ' << y << ' ' << v << '\n';
// }
/* 统计答案 */
SGT::build(1, 1, n);
std::cin >> Q;
for (int i = 1; i <= Q; i ++) {
int l, r, k;
std::cin >> l >> r >> k;
if (k == 1) {
ans[i] = SGT::ask(1, 1, n, l, r);
} else {
r --, k --;
seq.push_back({l, r, k, i});
}
}
scan1();
scan2();
for (int i = 1; i <= Q; i ++) {
std::cout << ans[i] << '\n';
}
return 0;
}
/**
* 心中无女人
* 比赛自然神
* 模板第一页
* 忘掉心上人
**/