图转侵删_(:з」∠)_
题解
隔k-1个位置设一个关键位 则每个区间都恰好包含一个关键位 预处理每个位置到左右关键位的前后缀积即可
题解
two pointers --------------------------------------------- hsz秒想出了另一种做法 所求答案为点对最小切比雪夫距离 旋转坐标系转换为曼哈顿距离 然后数据结构随便做 _(:з」∠)_居然还有这种操作
题解 令最终字符集S={1,2,...,|S|} 先把sa数组转成rank数组 发现rank数组就是一个|S|很大的原串 假设已经求出了|S|最小的原串，拿它和rank数组对比 sample: （在后面补零） sa 2 3 5 4 6 1 rank 6 1 2 4 3 5 0 原串 str 3 1 1 2 1 3 0 发现原串的每个字符（必定）对应rank中一段连续数字 这样我们的思路就打开了 顺理成章的，我们可以想想为什么1对应1,2,3却不能对应4 把找原串的过程想成通过合并数字减小字符集，则要保证合并数字时rank数组正确 可以猜测出可以合并的条件，令将合并的数字为k，合并的条件为 rank[sa[k-1]+1]<rank[sa[k]+1] 将4带入k发现不符合条件，而2,3符合 于是就有构造方法：从小到大合并数字，不能合并就多开一个集合，答案就是集合总数 正确性和最优性十分显然，证明不难，就不证了 这一拍脑袋出来的想法表述怎么那么复杂
