SP1487 PT07J - Query on a tree III 题解
sto_5k_orz
·
·
题解
谁告诉你这题不能莫队了。
考虑到如果是一条树上路径的话，那么可以用欧拉序，因为树上路径在欧拉序上是连续的。
但是子树呢？
考虑一颗子树在 dfs 序上是连续的，所以 dfs 序上莫队是可行的。
处理区间第 k 大，考虑值域分块。
所以查询时，先跳 $G_i$ 找出第 $k$ 大的块，然后块内暴力，复杂度 $\mathcal{O(n\sqrt n})$。
跑的飞快，直接最优解。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 100010; int cnt[N], a[N], n, q, k, ans[N];
struct Query {int id, l, r, k;} Q[N]; int now, in[N];
void add(int x) {cnt[x]++; if(cnt[x] == 1) now++;}
void del(int x) {cnt[x]--; if(!cnt[x]) now--;}
bool cmp(Query a, Query b) {return in[a.l] != in[b.l] ? in[a.l] < in[b.l] : a.r < b.r;}
vector<int> e[N]; int sz[N], D[N], d[N], tot;
void dfs(int u, int fa) {
sz[u] = 1; D[++tot] = u; d[u] = tot;
for(int v: e[u]) {
if(v == fa) continue;
dfs(v, u); sz[u] += sz[v];
}
}
int g[N], G[N], base, L[N], R[N], B, to[N];
void Add(int x) {g[x]++; G[in[x]]++;}
void Del(int x) {g[x]--; G[in[x]]--;}
int find(int k) {
int sum = 0, pos = -1;
for(int i = 1; i <= B; i++) {sum += G[i]; if(sum >= k) {pos = i; break;} }
// cout << "pos = " << pos << ' ' << G[pos] << '\n';
sum -= G[pos];
for(int i = L[pos]; i <= R[pos]; i++) {sum += g[i]; if(sum >= k) return i;}
return 114514;
}
int b[N];
int main() {
ios::sync_with_stdio(0); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
sort(b + 1, b + 1 + n); for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
// for(int i = 1; i <= n; i++) cout << a[i] << ' '; cout << '\n';
for(int i = 1; i <= n; i++) to[a[i]] = i;
for(int i = 1; i < n; i++) {
int a, b; cin >> a >> b;
e[a].push_back(b); e[b].push_back(a);
}
dfs(1, 0); cin >> q; base = sqrt(n); for(int i = 1; i <= n; i++) in[i] = (i + base - 1) / base; int x; B = in[n];
for(int i = 1; i <= B; i++) L[i] = (i - 1) * base + 1, R[i] = min(i * base, n);
for(int i = 0; i < q; i++) cin >> x >> Q[i].k, Q[i].l = d[x], Q[i].r = d[x] + sz[x] - 1, Q[i].id = i; int l = 1, r = 0; sort(Q, Q + q, cmp);
// for(int i = 0; i < q; i++) cout << Q[i].l << ' ' << Q[i].r << '\n';
// for(int i = 1; i <= n; i++) cout << D[i] << ' ';
for(int i = 0; i < q; i++) {
while(r < Q[i].r) Add(a[D[++r]]);
while(l > Q[i].l) Add(a[D[--l]]);
while(r > Q[i].r) Del(a[D[r--]]);
while(l < Q[i].l) Del(a[D[l++]]);
// cout << "l = " << l << " r = " << r << '\n';
// cout << "find = " << find(Q[i].k) << '\n';
ans[Q[i].id] = to[find(Q[i].k)];
}
for(int i = 0; i < q; i++) cout << ans[i] << '\n';
return 0;
}
```