SS241031D. 后缀数组（sa）

题意

重题：NOD2308D. 飒妃客厮 · 啊瑞（array）

给你一个初始 \(a_i=i\) 的长度为 \(n\) 的序列，\(n\le 10^9\)。

有 \(m\) 次操作。\(m\le 10^5\)。

1. 把区间 \([l,r]\) 移到最前面。
2. 翻转区间 \([l,r]\)。

最终得到序列 \(\{a_i'\}\)。

求满足长度为 \(n\) 的合法序列 \(\{b_i\}\) 的个数。一个合法的 \(b\) 满足其后缀数组是 \(a\) 且其值域连续（即最大的值等于其数字种类数）。

solution

对于 \(m\) 操作，因为有区间翻转，显然用文艺平衡树维护，可以感觉出需要使用动态开点平衡树，每个叶子维护一段区间而不是单个位置，具体维护什么信息取决于后面的推理。

假设我们已经得到了 \(\{sa_i\}\)，即上文的 \(\{a_i'\}\)。

合法序列只需要满足所有的后缀 \(sa_i\) 非严格小于后缀 \(sa_{i+1}\)（虽然也不可能存在两个完全相等的后缀吧，所以其实是严格小于啦）。

对于后缀 \(sa_i,sa_{i+1}\)，有两种情况：

1. \(b_{sa_i} < b_{sa_{i+1}}\)：此时 \(b_{sa_{i+1}}=b_{sa_i}+1\)，否则由于所有 \(sa_{1\sim i-1}\) 的后缀都小于后缀 \(sa_i\)，所有 \(sa_{i+2\sim n}\) 的后缀都大于后缀 \(sa_{i+1}\)，\(b\) 的值域将不满足连续性，因为如果存在 \(b_{sa_i} < b_k < b_{sa_{i+1}}\)，那么显然必定有 \(rk_{sa_i} < rk_k < rk_{sa_{i+1}}\)（定义 \(rk_{sa_i}=i\)）。
2. \(b_{sa_i} = b_{sa_{i+1}}\)：此时必定要求 \(rk_{sa_i+1} < rk_{sa_{i+1}+1}\)。

想象一下我们按照 \(sa_{1\sim n}\) 的顺序填写 \(b_{sa_i}\)，如果有 \(rk_{sa_i+1}<rk_{sa_{i+1}+1}\)，那么 \(b_{sa_{i+1}}\) 可以填 \(b_{sa_i}\) 或者 \(b_{sa_i}+1\) 两种，否则 \(b_{sa_{i+1}}\) 必须填 \(b_{sa_i}\) 一种。

因此问题变成计数有多少满足 \(rk_{sa_i+1}<rk_{sa_{i+1}+1}\)，假设有 \(cnt\) 个满足的，答案就是 \(2^{cnt}\)。

考虑如何计数。

我们的动态开点文艺平衡树维护了 \(O(m)\) 段斜率为 \(1\) 或者 \(-1\) 的线段，代表一段 \(sa\)。

在线段内部，一段上升的线段，其相邻两个 \(sa\) 一定满足要求。一段下降的线段，其相邻两个 \(sa\) 也一定满足要求。

在线段之间，一条线段末端的 \(sa\) 和后面一条线段的始端的 \(sa\) 满足要求，不好比较……

考虑把 \(sa\) 转化成 \(rk\) 数组，是好转化的，也是形如 \(O(m)\) 条上升 or 下降的线段。让刚刚那两个 \(sa\) 对应上 \(rk\) 的下标，然后直接比较 \(rk_{sa_x+1},rk_{sa_{x+1}+1}\) 就可以了，没什么技术难度。

这么看的话，题目的思维难度在于后缀数组相关要求的转化，而代码实现难度仅在于动态开点文艺平衡树上了。

时间复杂度 \(O(m\log m)\)，常数应该会比较大。

好【数据删除】难写