第46届ICPC亚洲区域赛（昆明）(正式赛） J.Just Another String Problem 题解
题目大意：
定义一个好集合 $T$：
所有元素均为字符串
$T$ 中不包含两个串 $p,q$，满足 $p$ 是 $q$ 的后缀
先给你一个长度为 $n$ 的字符串$s$，和一个长度为 $n$ 的数组 $v$。
一个好的集合 $T$ 的权值定义为 $\sum\limits_{s \in T} v_{|s|}$，其中 $|s|$ 表示字符串 $s$ 的长度。
然后 $q$ 次询问，每次给定两个数 $l,k$，问你当好集合 $T$ 的元素均为 $s_{1\dots l}$ 的子串，且 $T$ 的大小 $\le k$ 时，$T$ 的最大权值是多少。
- Lema 1. 最优情况下的 $T$ 中的所有串都是 $s$ 的前缀
可以反证。
如果其中有一个串 $p$ 不是 $s$ 的前缀，设 $p=s_{l\dots r}$，那么我们让 $p=s_{1\dots r}$ 答案一定不会劣。
首先，题目中保证了 $v_i$ 单调增，所以这个新 $T’$ 的权值一定会更大。
然后，我们来说明这个 $T’$ 是合法的。
还是反证，假设这个 $p’=s_{1 \dots r}$ 是某个串 $q$ 的后缀。
那么显然，由于 $p$ 是 $p’$ 的后缀，$p’$ 又是 $q$ 的后缀，所以 $p$ 就是 $q$ 的后缀，然而 $p$ 和 $q$ 均在原来的 $T$ 中，故 $T$ 不合法，而原来的 $T$ 是合法的，矛盾、
- Lema 2. 对于每一个 $1\le i \le n$，我们最多选择一个串满足结尾为 $i$
由引理1易证，同一个串不能出现两次。
- Lema 3. 对于两个不同的 $1 \le i < j \le n$，以 $j$ 结尾的串的权值一定大于 $i$ 的
引理1和2可以得到只能选择$s_{1\dots i}$ 和 $s_{1 \dots j}$，又由 $v_j\geq v_i$ 可得。
由引理1可得，我们考虑两个前缀什么时候不能出现。
考虑 kmp 建出的 fail 数组并把它拎成一棵fail树，那么对于长度为 $j$ 的前缀和长度为 $i$ 的前缀（ $i \le j$ ）不能同时出现，当且仅当 $i$ 不是 $j$ 的祖先。
$fail_i$ 的定义：$fail_i<i$，且 $s_{1\dots fail_i}$ 是最长的既是 $s_i$ 的前缀又是后缀的串。
由定义得当 $i=fail_j$ 的时候 $i$ 和 $j$ 不能同时出现。
然后我们考虑 $t=fail_{fail_{j}}$，由于$s_{1\dots t}$ 为 $s_{1\dots fail_j}$ 的前缀和后缀，而 $s_{1\dots fail_j}$ 是 $s_{1 \dots j}$ 的前缀和后缀，所以 $s_{1\dots t}$ 是 $s_{1 \dots j}$ 的前缀和后缀。递归下去就可以推出是祖先就不能出现的结论了。
最后我们要做的，就是把询问离线，按照 $l$ 从小到大排序，依次加入 $s_i$ ，维护一棵线段树即可。
由引理3可得，选择越靠后的串总权值越大，就可以用主席树查询区间第 $k$ 大的方法来求答案了。
Code:
1 |
|