1003

一个 01 串 $s$ 可以被重写成 $kp+p’$，其中 $p’$ 是 $s$ 的一个可以为空的前缀，给定 $n$ ，求所有长度为 $n$ 的 $01$ 串的重写后最大的 $k$​ 的和。

1004

给每个字符一个权值 $c_i$​​ ，定义串的价值是他所有字符的权值和，求一个串所有的本质不同子串第 $k$​​​​ 小的权值是多少？不存在输出 $-1$ 。

($1 \leq c_\alpha\leq 100,1\leq n \leq 10^5,1 \leq k\leq \frac{n(n+1)}{2}$​​​)

子串是后缀的前缀。

后缀数组的 $height$ 可以去重解决本质不同子串的问题，并找到相应的位置。

找第 $k$ 经典套路，二分答案，只需 $check$​ 比这个值小的出现次数即可。

因为一个后缀的前缀权值是递增的，可以二分找右端点数这个后缀的本质不同的子串有几个小于 $check$ 的值。

复杂度 $O(nlog_2wlog_2n)$

双指针处理一下正常顺序下，每个点开始的右端点，考虑先得到不管本质不同的子串有几个的答案，在按 $sa_i$​​ 顺序遍历减去重复的子串符合条件的个数即可。

复杂度 $O(nlog_2w)$

1005

$n$​ 个数的序列， $m$​ 次询问在 $[l,r]$​ 区间等概率选子区间 $[x,y]$​ ，即 $(1 \leq l \leq x \leq y \leq r \leq n)$​​ 求子区间 $\frac{max+min}{2}$​ 的期望。

$(1 \leq n,m \leq 2 \times 10^5)$

关键在询问，不然单调栈算每个数贡献直接做完了。

具体来说，对于一个询问，只需要求每个数作为最大值出现的次数和最小值出现的次数就能得到分子。

$$ \frac{\sum _{i = l}^r a_i * cnt_X+a_i * cnt_Y } {len*(len+1)/2*2} $$

$X$ 和 $Y$ 表示以这个数为最大值或最小值事件。

多次询问怎么解决，发现是有原题的。

不妨先只考虑怎么数，一个区间子区间内每个数作为最小值出现次数的和。

对于一个区间，已知他的最小值所在位置是 $p$，那么这个点对答案的贡献是 $a_p*(r-p+1)*(p-l+1)$ ，我们考虑根据这个最小值，把答案切成两个子区间 $[l,p-1]$ ，$[p+1,r]$ 在求这两个子区间内的答案。

先只考虑对右区间求解

考虑设这样一个函数

$f_{l,r}$ 表示说所有恰好以 $r$ 为右端点，左端点是 $l,l+1…,r$ 的区间的答案。

转移显然是从上一个比 $a_r$ 小的地方转移过来，中间的一系列左端点到 $r$ 都是以 $a_r$ 为最小值的，记 $pre_i$ 表示上一个比 $a_i$​ 小的位置 $$ f_{l, r}= f_{l, pre_r}+a_r*(r-pre_r) $$ 发现这个第一维 $l$​​ 似乎根本没必要，只要能一直找到前缀更小的位置的转移点就可以直接做。

就可以写成 $$ f_r = a_r (r-pre_r)+…+a_x(x-p)+f_p $$ 那么一定存在一个位置点 $x$​ ， $pre_x=p$​ ，这个 $p$​ 就是我们前面求的最小值的位置，那么所有恰好以 $r$​ 为右端点，左端点是 $p+1…r$​ 的区间的答案就是 $f_r-f_p$​​​。

是不是很对啊，​​​这么做对的前提是 $p$ 一定是 $r$​​ 的转移点才对。

那么考虑对右边的区间 $[p+1,r]$

对于 $r$​ 来说，所有恰好以 $r$​ 为右端点，左端点是 $p+1…,r$​ 的区间的答案是 $f_r-f_p$​​ 。

对于 $r-1$​​​​ 来说，所有恰好以 $r-1$​​​​ 为右端点，左端点是 $p+1…,r-1$​​​​ 的区间的答案是 $f_{r-1}-f_p$​​​​ 。

…

对于 $p+1$​​​​​​​ 来说，所有恰好以 $p+1$​​​​​​​ 为右端点，左端点是 $p+1…p+1$​​​​​​​ 的区间的答案是 $f_{p+1}-f_p$​​​​​​ ​。

显然可以前缀和优化，记 $g_i=\sum_{j=1}^{i}f_i$​ 。

那么所有右边区间 $[p+1,r]$​​​ 的答案为 $g_r-g_p-f_p*(r-p)$​​ 。

左边区间也可以类似处理，要维护一个后缀的类似的数组，因为此时 $p$ 在右侧。

这题这样对最大值和最小值分别搞一次，就做完了。