日记详情

回顾由 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)\)。

\(cnt\) 容易扫描线求出。于是问题转化为多次询问 \([0,r)\) 中第 \(k\) 个满足 \(a_p\geq u\lor nxt_p<r\) 的位置 \(p\)。

考虑离线下来整体二分。设当前分治区间为 \([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)\)。

代码细节很多。

代码

#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;
}