给出字符串 \(s\)，以及数组 \(a_1\sim a_{|s|}\)。
定义一个子串的排名为：字典序比它大的本质不同的子串个数 \(+1\)。
定义一个子串 \(s[l,r]\) 的权值为 \(\sum\limits_{i=l}^ra_i\)。
求有多少个子串的排名等于权值。
\(|s|\le 10^5,0\le a_i\le 1000\)。
首先对 \(s\) 进行后缀排序，然后考虑每一个左端点 \(l\)，不难发现随着右端点 \(r\) 的增大，子串的排名单调递减，权值单调不降。
所以可以二分出满足条件的最小 / 大右端点。
考虑如何求出一个子串 \(t\) 的排名。可以用本质不同子串数减去比它小的。
前半部分运用经典结论即为 \(\sum\limits_{i=1}^n (|s|-sa_i+1-\text{height}_i)\)，我们考虑如何求比它小的本质不同子串数。
可以二分出以这个子串为前缀的后缀排名区间 \([L,R]\)。答案即为排名为 \(\boldsymbol{[1,L)}\) 的后缀带来的本质不同子串个数。
-
充分性：
若一个子串 \(str\) 在排名为 \([1,L)\) 的后缀中作为前缀出现，那么这个后缀 \(s[i,|s|]\) 与 \(s[l,|s|]\) 的 \(\text{LCP}\) 长度一定小于 \(\boldsymbol{|t|}\)。即两个后缀可以在第 \(|t|\) 个位置之前可以找到不相同的位置。而由于 \(s[i,|s|]\) 这个后缀排名更小，在这个位置一定 \(s[i,|s|]\) 这个后缀小于 \(s[l,|s|]\)。
考虑 \(str\) 是否跨过这个位置，若不是，则在前 \(|str|\) 位两串相同，第 \(|str|+1\) 位 \(str\) 为空，字典序极小。
若跨过，则 \(str\) 在这个位置小于 \(t\)。
-
必要性：
考虑这两个子串第一次不同是在某个位置，这个位置一定在两个后缀中。
正确性证好了。这个东西也是考虑每个后缀带来的本质不同子串。即可以这么求：
\[\sum\limits_{i=1}^{L-1}(|s|-sa_i+1-\text{height}_i) \]于是做完了。时间复杂度为 \(\mathcal{O}(|s|\log^2|s|)\)，空间复杂度为 \(\mathcal{O}(|s|)\)。
标签：子串,后缀,题解,位置,矿石,str,text,排名,P4143 From： https://www.cnblogs.com/MnZnOIerLzy/p/17872098.html