题解：P17144 [NOI 2026] 木棉
P2441M
·
·
题解
回顾由 Prüfer 序列还原一棵树的过程：令 deg_u=cnt_u+1，从小到大枚举 0\leq i<n-2，每次取编号最小的叶子节点 u，加入边 (u,a_i)。最后剩下的两个叶子节点之间再连一条边。
设 pos_r(u) 表示 u 在 a[0..r) 中最后一次出现的位置，若没有出现则记为 -1。那么 u 从 t_u=\max(pos_r(u)-l+1,0) 时刻开始才可能成为叶子。
显然只有 <u 的点可能阻碍 u 成为编号最小的叶子，不妨设 q_u 表示最早的时刻使得不存在 <u 的点为编号最小的叶子。
容易发现 u 被删除的时刻就是 \max(t_u,q_u)。因此考虑如何求出 q_u。
观察到 q_u 是满足
q_u=\sum_{v<u}[t_v\leq q_u]=\sum_{v<u}[pos_r(v)<l+q_u]
的最小整数。
考虑对于每个在 a[0..r) 中出现的 v<u，在 pos_r(v) 处打一个标记。设 a[0..r) 中出现了 cnt 个 <u 的数，那么 [0,l+q_u) 中有 q_u-u+cnt 个标记，也就有 l+u-cnt 个没有被标记的位置。于是我们只需要找出第 l+u-cnt 个没有被标记的位置 p，那么 q_u=\max(p-l+1,-1)。
考虑离线下来整体二分。设当前分治区间为 $[L,R]$，中点为 $mid$。对于每个询问，考虑 $[L,mid]$ 中满足 $a_p<u\land nxt_p\geq r$ 的 $p$ 的个数 $x$。这个是二维偏序的形式，容易扫描线求出。那么 $[L,mid]$ 中就有 $mid-L+1-x$ 个没有被标记的位置，将其和 $k$ 进行比较递归下去即可。
注意若 $u=r-l+1$ 则 $u$ 被删除的时刻就是 $r-l$；否则 $u<r-l+1$，此时 $<u$ 的限制自然允许我们不必再去考虑取 $\min$ 的问题。
设 $u,v$ 被删除的时刻分别为 $d_u,d_v$。那么 $u,v$ 间有连边当且仅当满足下面的条件之一：
- $d_u<r-l\land \min(a_{l+d_u},r-l+1)=v$。
- $d_v<r-l\land \min(a_{l+d_v},r-l+1)=u$。
- $d_u=r-l\land d_v=r-l$。
时间复杂度为 $\mathcal{O}((n+q)\log^2n)$。
代码细节很多。
:::success[代码]
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128;
using ui = unsigned int;
using ull = unsigned long long;
using u128 = unsigned __int128;
using ld = long double;
using pii = pair<int, int>;
const int MAXN = 2e5 + 5, LOGN = 20;
template<typename T> T lowbit(T x) { return x & -x; }
template<typename T> void chkMin(T &x, T y) { x = y < x ? y : x; }
template<typename T> void chkMax(T &x, T y) { x = x < y ? y : x; }
constexpr int lg2(ll x) { return 63 ^ __builtin_clzll(x); }
constexpr ll bitCeil(ll x) { return x == 1 ? 1ll : 1ll << lg2(x - 1) + 1; }
struct BIT {
int sz, c[MAXN];
void init(int n) {
sz = n;
fill(c + 1, c + sz + 1, 0);
}
int query(int x) {
int res = 0;
for (++x; x; x -= lowbit(x)) res += c[x];
return res;
}
void add(int x, int v) {
for (++x; x <= sz; x += lowbit(x)) c[x] += v;
}
} ft;
struct Query1 {
int id, tp, r, x;
};
struct Query2 {
int id, tp, k, u, r;
};
vector<Query1> queries1;
vector<Query2> queries2;
array<int, 2> cnt[MAXN], q[MAXN], t[MAXN];
int pos[MAXN], nxt[MAXN];
int ord[LOGN][MAXN];
vector<bool> kapok(int c, int n, int m, vector<int> a, vector<int> l, vector<int> r, vector<int> x, vector<int> y) {
for (int i = 0; i < m; ++i) {
int len = r[i] - l[i] + 1;
if (x[i] != len) queries1.push_back({i, 0, r[i], x[i]});
else t[i][0] = len - 1;
if (y[i] != len) queries1.push_back({i, 1, r[i], y[i]});
else t[i][1] = len - 1;
q[i][0] = q[i][1] = -1;
}
sort(queries1.begin(), queries1.end(), [&](const Query1 &lhs, const Query1 &rhs) {
return lhs.r < rhs.r;
});
ft.init(n + 2);
fill(pos, pos + n + 2, -1);
for (int r = 0, i = 0; r <= n; ++r) {
while (i < queries1.size() && queries1[i].r <= r) {
auto [id, tp, r, x] = queries1[i++];
int cnt = ft.query(x - 1);
t[id][tp] = max(pos[x] - l[id] + 1, 0);
int k = l[id] + x - cnt;
if (k) queries2.push_back({id, tp, k, x, r});
else q[id][tp] = -1;
}
if (r == n) break;
if (pos[a[r]] == -1) ft.add(a[r], 1);
pos[a[r]] = r;
}
fill(pos, pos + n + 2, n);
for (int i = n - 1; i >= 0; --i) {
nxt[i] = pos[a[i]];
pos[a[i]] = i;
}
auto build = [&](auto &&self, int dep, int L, int R) -> void {
if (L == R) {
ord[dep][L] = L;
return;
}
int mid = L + R >> 1;
self(self, dep + 1, L, mid);
self(self, dep + 1, mid + 1, R);
int i = L, j = mid + 1, k = L;
while (i <= mid && j <= R) {
int x = ord[dep + 1][i], y = ord[dep + 1][j];
if (nxt[x] >= nxt[y]) {
ord[dep][k++] = x;
++i;
} else {
ord[dep][k++] = y;
++j;
}
}
while (i <= mid) ord[dep][k++] = ord[dep + 1][i++];
while (j <= R) ord[dep][k++] = ord[dep + 1][j++];
};
build(build, 0, 0, n - 1);
auto solve = [&](auto &&self, int dep, int L, int R, vector<int> &qid) -> void {
if (qid.empty()) return;
if (L == R) {
for (int p : qid) {
auto [id, tp, k, u, r] = queries2[p];
q[id][tp] = L;
}
return;
}
int mid = L + R >> 1;
vector<int> qrL, qrR;
int p = L;
for (int i = 0; i < qid.size(); ++i) {
int pos = qid[i];
auto &[id, tp, k, u, r] = queries2[pos];
while (p <= mid && nxt[ord[dep + 1][p]] >= r) ft.add(a[ord[dep + 1][p++]], 1);
int ans = ft.query(u - 1);
if (mid - L + 1 - ans >= k) {
qrL.emplace_back(pos);
} else {
k -= mid - L + 1 - ans;
qrR.emplace_back(pos);
}
}
while (p > L) ft.add(a[ord[dep + 1][--p]], -1);
self(self, dep + 1, L, mid, qrL);
self(self, dep + 1, mid + 1, R, qrR);
};
ft.init(n + 2);
reverse(queries2.begin(), queries2.end());
vector<int> qid(queries2.size());
iota(qid.begin(), qid.end(), 0);
solve(solve, 0, 0, n - 1, qid);
vector<bool> ans(m);
for (int i = 0; i < m; ++i) {
if (x[i] == y[i]) {
ans[i] = false;
continue;
}
int len = r[i] - l[i] + 1;
int mx1 = max(t[i][0], max(q[i][0] - l[i] + 1, -1)), mx2 = max(t[i][1], max(q[i][1] - l[i] + 1, -1));
ans[i] = (mx1 < len - 1 && min(a[l[i] + mx1], len) == y[i]) || (mx2 < len - 1 && min(a[l[i] + mx2], len) == x[i]) || (mx1 == len - 1 && mx2 == len - 1);
}
return ans;
}
```
:::