P5346 【XR-1】柯南家族
xht
·
·
题解
题目地址：P5346 【XR-1】柯南家族
Q：官方题解会咕么？
A：不会！（大雾
题解环节
首先，我们假设已经求出了 n 个人聪明程度的排名。
对于 $op = 2$ 和 $op = 3$，由于求第 $k$ 大很容易想到主席树。
$op = 2$ 只需要在节点的父亲版本上更新即可。
$op = 3$ 只需要按照 $dfs$ 序更新即可。
那么 $op = 2$ 和 $op = 3$ 可以做到单次 $O(\log n)$ 回答。
以上都挺套路的，现在的问题在于，如何 $sort$。
### 算法一：暴力
直接模拟比较方式即可，这里给出比较函数。
```cpp
inline bool cmp(int x, int y) {
int fx = x, fy = y;
while (fx != fy && a[fx] == a[fy]) {
x = fx, y = fy;
fx = f[fx], fy = f[fy];
}
return a[fx] < a[fy] || (a[fx] == a[fy] && x < y);
}
```
然后直接调用 $sort$ 函数即可，时间复杂度 $O(n^2)$，期望得分 $14$ 分。
### 算法二：树上倍增 + 哈希
这是应该算是对暴力的优化。
```cpp
//g[x]:log(x)
//d[x]:x的深度
//h[x]:从根节点到x的哈希值
//f[i][x]:树上倍增中x的第i祖先
//H(x,y):x到y的哈希值
inline bool cmp(int x, int y) {
int w = g[min(d[x],d[y])];
if (h[x] != h[y]) {
for (int i = w; ~i; i--)
if (H(f[i][x], x) == H(f[i][y], y)) {
x = f[0][f[i][x]];
y = f[0][f[i][y]];
}
if (a[x] == a[y]) {
x = f[0][x];
y = f[0][y];
}
return a[x] < a[y];
} else {
for (int i = w; ~i; i--)
if (f[i][x] != f[i][y]) {
x = f[i][x];
y = f[i][y];
}
return x < y;
}
}
```
需要预处理一大堆东西，然后仍然直接调用 $sort$ 函数即可，时间复杂度 $O(n \log ^ 2 n)$，期望得分 $32$ 分。
~~没错，两只 $\log$ 很成功的被我卡掉了。~~
### 算法三：后缀排序 SA
考虑部分分：
> 对于另 $20\%$ 的数据，保证一个人最多只有一个儿子，每个测试点 $9$ 分，时限 4s。
即整个家族形成一条链。
那么其实这就是一个以 $n$ 节点为头，根节点为尾的字符串，而题目所要求的其实就是后缀排序。
由于智商值的规模高达 $10^9$ ，离散化一下，然后使用 SA 进行排序即可，时间复杂度 $O(n \log n)$ ，期望得分 $18$ 分，结合方法二可以得到 $50$ 分。
### 算法四：
看一眼数据范围 $1 \le n \le 5 \times 10 ^ 5$，这显然要求我们用一种 $O(n \log n)$ 的算法进行排序。
受到方法三的启发，我们能不能把 SA 搬到树上呢？
于是，我们需要引入**树上 SA**。
### 模板：[【模板】树上后缀排序](https://www.luogu.org/problemnew/show/P5353)
~~为了写篇题解我还造了道模板题。~~
我们尝试把普通 SA 改成树上 SA，所以先把普通 SA 贴上来。
```cpp
namespace SA {
int sa[N], rk[N], tp[N], tx[N];
inline void tsort() {
for (int i = 1; i <= m; i++) tx[i] = 0;
for (int i = 1; i <= n; i++) ++tx[rk[i]];
for (int i = 1; i <= m; i++) tx[i] += tx[i-1];
for (int i = n; i; i--) sa[tx[rk[tp[i]]]--] = tp[i];
}
inline bool pd(int i, int w) {
return tp[sa[i-1]] == tp[sa[i]] && tp[sa[i-1]+w] == tp[sa[i]+w];
}
inline void main() {
for (int i = 1; i <= n; i++) rk[i] = s[i] - 'a' + 1, tp[i] = i;
tsort();
for (int w = 1, p = 0; p < n; w <<= 1, m = p) {
p = 0;
for (int i = 1; i <= w; i++) tp[++p] = n - w + i;
for (int i = 1; i <= n; i++) if (sa[i] > w) tp[++p] = sa[i] - w;
tsort(), swap(rk, tp), rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) rk[sa[i]] = pd(i, w) ? p : ++p;
}
}
}
```
想要把普通 SA 改成树上 SA，仔细观察上面的代码可以发现：
1. $tsort$ 函数肯定是不用改的；
2. $pd$ 函数可以用树上倍增实现；
3. $main$ 函数似乎也很好改？
于是开始改改改，突然发现有个问题：**由于序列上每个后缀长度都不一样，所以不可能出现完全相同的字符串，可是在树上是可能出现这种情况的。**
然后就没办法了么？
办法肯定是有的~~要不然这道题是咋出出来的~~。
我们来思考一下，在倍增的每一轮，**基数排序**究竟要达到什么目的？
对于普通 SA，在倍增的每一轮，假设已经对所有长度为 $x$ 的串排好序了。“第一关键字”和“第二关键字”代表了两个首尾相接的长度为 $x$ 的串，称为“主串”和“次串”。基数排序通过 $O(n)$ 的时间，将每一对“主串”和“次串”**合并**成一个长度为 $2x$ 的新串并保持合并后**有序**。
这样可以保证 $O(\log n)$ 次后，所有后缀呈有序状态。
对于树上 SA，也是同样的。只不过，除了“主串”作为第一关键字，“次串”作为第二关键字以外，为了保证合并后的有序性，我们还要额外将上一轮的有序状态作为第三关键字。同时第二关键字也不能简单地用原先的 $rk$ 数组构造（因为 $rk$ 数组会出现相同的排名），而要额外使用没有重复的数组（下面代码中的 $rkk$ 数组）构造。
总而言之，我们需要使用两次基数排序来达到目的，具体实现请参考代码~~因为这说得实在是太抽象了~~：
```cpp
namespace SA {
int sa[N], rk[N], rkk[N], tp[N], rk2[N], tx[N];
inline void tsort(int *sa, int *rk, int *tp, int m) {
for (int i = 0; i <= m; i++) tx[i] = 0;
for (int i = 1; i <= n; i++) ++tx[rk[i]];
for (int i = 1; i <= m; i++) tx[i] += tx[i-1];
for (int i = n; i; i--) sa[tx[rk[tp[i]]]--] = tp[i];
}
inline bool pd(int i, int t) {
return tp[sa[i-1]] == tp[sa[i]] && tp[f[t][sa[i-1]]] == tp[f[t][sa[i]]];
}
inline void main() {
int p = 0;
for (int i = 1; i <= n; i++) a[i] = s[i] - 'a' + 1, tp[i] = i;
tsort(sa, a, tp, n);
rk[sa[1]] = rkk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = a[sa[i-1]] == a[sa[i]] ? p : ++p;
rkk[sa[i]] = i;
}
for (int w = 1, t = 0; w < n; w <<= 1, ++t) {
for (int i = 1; i <= n; i++) rk2[i] = rkk[f[t][i]];
tsort(tp, rk2, sa, n);
tsort(sa, rk, tp, p);
swap(rk, tp);
rk[sa[1]] = rkk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = pd(i, t) ? p : ++p;
rkk[sa[i]] = i;
}
}
}
}
```
~~当然也许还有其他写法。~~
有了树上 SA，原题就很简单了~~就是个板子~~，下面贴上 std：
```cpp
#include <bits/stdc++.h>
using namespace std;
namespace IO {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
inline void flush() {
fwrite(obuf, 1, oS - obuf, stdout);
oS = obuf;
}
inline void putc(char x) {
*oS++ = x;
if (oS == oT) flush();
}
template <class I>
inline void rd(I &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc())
if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc())
x = x * 10 + (c & 15);
x *= f;
}
template <class I>
inline void print(I x) {
if (!x) putc('0');
if (x < 0) putc('-'), x = -x;
while (x) qu[++qr] = x % 10 + '0', x /= 10;
while (qr) putc(qu[qr--]);
putc('\n');
}
struct Flusher_ {
~Flusher_() {
flush();
}
} io_flusher_;
}
using IO::rd;
using IO::print;
const int N = 5e5 + 6;
int n, q, f[21][N], a[N], b[N];
vector<int> e[N];
namespace SA {
int sa[N], rk[N], rkk[N], tp[N], rk2[N], tx[N];
inline void tsort(int *sa, int *rk, int *tp, int m) {
for (int i = 0; i <= m; i++) tx[i] = 0;
for (int i = 1; i <= n; i++) ++tx[rk[i]];
for (int i = 1; i <= m; i++) tx[i] += tx[i-1];
for (int i = n; i; i--) sa[tx[rk[tp[i]]]--] = tp[i];
}
inline bool pd(int i, int t) {
return tp[sa[i-1]] == tp[sa[i]] && tp[f[t][sa[i-1]]] == tp[f[t][sa[i]]];
}
inline void main() {
int p = 0;
for (int i = 1; i <= n; i++) tp[i] = i;
tsort(sa, a, tp, n);
rk[sa[1]] = rkk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = a[sa[i-1]] == a[sa[i]] ? p : ++p;
rkk[sa[i]] = i;
}
for (int w = 1, t = 0; w < n; w <<= 1, ++t) {
for (int i = 1; i <= n; i++) rk2[i] = rkk[f[t][i]];
tsort(tp, rk2, sa, n);
tsort(sa, rk, tp, p);
swap(rk, tp);
rk[sa[1]] = rkk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = pd(i, t) ? p : ++p;
rkk[sa[i]] = i;
}
}
for (int i = 1; i <= n; i++) a[i] = rkk[i];
}
}
namespace Seg {
struct T {
int l, r, c;
} t[2][N*20];
int tot[2], rt[2][N], dfn[N], s[N], num;
inline int ins(int o, int p, int l, int r, int x) {
int q = ++tot[o];
t[o][q] = t[o][p];
++t[o][q].c;
if (l ^ r) {
int mid = (l + r) >> 1;
if (x <= mid) t[o][q].l = ins(o, t[o][p].l, l, mid, x);
else t[o][q].r = ins(o, t[o][p].r, mid + 1, r, x);
}
return q;
}
inline int ask(int o, int p, int q, int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) >> 1, rc = t[o][t[o][q].r].c - t[o][t[o][p].r].c;
if (k <= rc) return ask(o, t[o][p].r, t[o][q].r, mid + 1, r, k);
return ask(o, t[o][p].l, t[o][q].l, l, mid, k - rc);
}
inline void dfs(int x) {
dfn[x] = ++num;
rt[1][num] = ins(1, rt[1][num-1], 1, n, a[x]);
s[x] = 1;
for (unsigned int i = 0; i < e[x].size(); i++) {
int y = e[x][i];
rt[0][y] = ins(0, rt[0][x], 1, n, a[y]);
dfs(y);
s[x] += s[y];
}
}
inline void main() {
rt[0][1] = ins(0, 0, 1, n, a[1]);
dfs(1);
while (q--) {
int o, x;
rd(o), rd(x);
if (o == 1) print(n + 1 - a[x]);
else {
int k;
rd(k);
if (o == 2) print(SA::sa[ask(0, 0, rt[0][x], 1, n, k)]);
else print(SA::sa[ask(1, rt[1][dfn[x]-1], rt[1][dfn[x]+s[x]-1], 1, n, k)]);
}
}
}
}
int main() {
rd(n), rd(q);
for (int i = 2; i <= n; i++) {
rd(f[0][i]);
e[f[0][i]].push_back(i);
}
int t = 0;
bool flag = 1;
while (flag && ++t) {
flag = 0;
for (int i = 1; i <= n; i++)
if ((f[t][i] = f[t-1][f[t-1][i]])) flag = 1;
}
for (int i = 1; i <= n; i++) {
rd(a[i]);
b[i] = a[i];
}
sort(b + 1, b + n + 1);
int p = unique(b + 1, b + n + 1) - (b + 1);
for (int i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, b + p + 1, a[i]) - b;
SA::main();
Seg::main();
return 0;
}
```
~~代码不长，也就 $4k$。~~
### 算法五：
比赛时有两个人 AC 了此题：[租酥雨](https://www.luogu.org/space/show?uid=47654)，[究极龙骑士](https://www.luogu.org/space/show?uid=47803)。
先 Orz ~~这叫官方膜拜。~~
他们用的都是替罪羊树维护~~不知道是不是叫后缀平衡树~~。
~~然而我甚至不会替罪羊树。~~
这个方法现在已知有两个人写了题解：[Owen_codeisking](https://www.luogu.org/blog/Owencodeisking/solution-p5346)，[dsidsi](https://blog.csdn.net/DSL_HN_2002/article/details/89854445)。
那我就不写了~~反正本来就不会。~~
总结一下这两篇题解的共性：都参考[租酥雨](https://www.luogu.org/space/show?uid=47654)的代码~~还都 diss 了窝（委屈~~。
## 故事环节
### idea 来源
~~凭空想到的。~~
一开始的想法是，树上**倍增**和 SA 的**倍增**可以结合一下嘛。
然后后来就搞出了树上 SA 这么个东西。
后来 World Final 有道题似乎要用树上 SA ~~不过听说被出题人对着卡？~~
当时还因为奶中了 WF 的算法兴奋了好一阵子。
~~然后省选就凉了。~~
### 彩蛋
不知道大家有没有发现本场比赛的彩蛋呢？
本场比赛的日期是 05-04，这个日期是不是有什么特殊的意义呢？
> 江户川柯南：真实身份是高中生侦探工藤新一。$17$ 岁，因服下毒药身体变小后约 $7$ 岁。生日是 $5$ 月 $4$ 日，来源于 $1891$ 年 $5$ 月 $4$ 日福尔摩斯和莫里亚蒂教授坠入莱辛巴赫瀑布的日期。
>
> 工藤新一： $17$ 岁的高中生侦探。生日为 $5$ 月 $4$ 日，来源于《福尔摩斯探案集之最后一案》中， $1891$ 年 $5$ 月 $4$ 日福尔摩斯和莫里亚蒂教授在莱辛巴赫瀑布展开对决，莫里亚蒂掉到瀑布里死亡，福尔摩斯生还。
**祝柯南和新一生日快乐！**
没了么？
~~还有么？~~
这是 xht37 在洛谷的个人信息：
> - **用户 ID** 100544
> - **用户类型** 普通用户
> - **注册时间** 2018-05-04 08:29
**xht37 来洛谷已经整整一年啦 QwQ**