不需要文件IO

题解

A、ratio

简单将题目中的 $\frac{a_i a_j}{a_i+a_j}>k$ 变形为 $\frac{a_i+a_j}{a_i a_j}=\frac{1}{a_i}+\frac{1}{a_j}<k$ ，我们不妨考虑 $\frac{1}{a_i}+\frac{1}{a_j}\ge k$ 的个数，然后再从全部里面减掉这部分。

不妨假设 $a_i\le a_j$ ，不难发现，如果 $a_i\le k$ 时一定可行，而 $a_i>2k$ 时一定不可行，所以我们先开一个桶（map或哈希表）记录每种数字出现了多少次，然后直接枚举 $a_i$ ，此时可行的 $a_j$ 不会超过 $k(k+1)$ ，继续枚举可能的 $a_j$ 即可。

复杂度为 $O(n+k^3)$ 。（当然你也可以写树状数组 $O(n\log(n))$ ）

B、perm

我们发现这题中所有的约束条件都是对于相邻的两个元素的，所以对于任意一个前缀，有用的信息就只有末尾位置。

我们可以写出一个 dp，$f_{i,j}$ 表示对于前 $i$ 个数将 $1,2,\cdots,i$ 填进去，第 $i$ 个数是 $j$ 的方案数，转移如下：

$$s_i=0,f_{i+1,j}=\sum_{k=j}^{i} f_{i,k}\\ s_i=1,f_{i+1,j}=\sum_{k=1}^{j-1} f_{i,k} $$

直接转移是 $O(n^3)$ 的，不难发现每个转移对应一个前缀和，可以直接求出前缀和，所以总复杂度为 $O(n^2)$ 。

C、stone

• 引理：最终每堆石子数所形成的每种序列一共有 $\binom{n+m-1}{n-1}$ 种，其中每种出现概率均相同，均为 $\frac{1}{\binom{n+m-1}{n-1}}$ 。

证明：我们考虑任意一种序列 $a_1,a_2,\cdots,a_n$ ，一共有 $\frac{m!}{\prod_{i=1}^{n}(a_i-1)!}$ 种操作序列到达这个状态，其中每种操作序列的出现概率为 $\frac{\prod_{i=1}^{n}(a_i-1)!}{n^{\overline{m}}}$ 。所以这个序列的出现概率就是：

$$\frac{m!}{\prod_{i=1}^{n}(a_i-1)!}\times \frac{\prod_{i=1}^{n}(a_i-1)!}{n^{\overline{m}}}=\frac{m!(n-1)!}{(n+m-1)!}=\frac{1}{\binom{n+m-1}{n-1}} $$

我们不妨把最终序列的每个位置减去 $1$ ，现在我们的问题就转化为 $a_1+a_2+...+a_n=m$ 的所有非负整数解中第 $k$ 大数字的期望。

考虑求出所有方案的总和后再除以 $\frac{1}{\binom{n+m-1}{n-1}}$ ，我们可以设计一个dp $f_{i,j}$ 表示对于 $a_1+a_2+\cdots+a_i=j$ 的所有非负整数解中第 $k$ 大数字的期望。

对于这个dp的转移，我们可以枚举这个 $a_1,a_2,\cdots,a_n$ 中大于 $0$ 的数字个数 $t$ ，这样我们就可以只保留这些大于 $0$ 的数，然后把它们全部减去 $1$ 得到 $f_{t,j-t}$ 这个子问题，具体转移方程如下：

$$f_{i,j}=\sum_{t=0}^{i} \binom{i}{t}(f_{t,j-t}+[t\ge k]\binom{j-1}{t-1}) $$

$\binom{i}{t}$ 表示选取大于 $0$ 的数的所在位置， $[t\ge k]\binom{j-1}{t-1}$ 表示加 $1$ 的时候对第 $k$ 大数的和的贡献， $\binom{j-1}{t-1}$ 即为 $f_{t,j-t}$ 的方案数。

总复杂度 $O(n^3)$ 。

D、seq

我们考虑把序列按照 $C$ 分段，即连续不超过 $C$ 个数为一段，显然合法的子段至多跨越两个整块，那现在我们的询问操作可以被拆解为三个部分，整块块内，整块块间和散块与整块。

我们先来考虑散块与散块怎么解决，假设散块区间为 $[l_1,r_1]$ 和 $[l_2,r_2]$ ($l_2=r_1+1$) ，若两个散块区间的长度之和不超过 $C$ ，可以直接询问 $[l_1,r_2]$ 的最大子段和，否则我们先询问 $[l_1,l_1+C)$ 和 $(r_2-C,r_2]$ 的最大子段和，然后计算左端点在 $[l_1,r_2-C]$ 内，右端点在 $[l_1+C,r_2]$ 内且长度不超过 $C$ 的最大子段和。

我们可以考虑对于每相邻两个整块开一棵线段树，其中第 $i$ 个位置存储左边整块的长度为 $C-i$ 后缀和以及右边整块的长度为 $i$ 的前缀和，这样在合并的时候可以快速维护又左右儿子合并上来的长度不超过 $C$ 的最大子段和。这样在查询散块与散块之间的最大子段和就可以变为一个区间查询。散块与整块之间同理。

修改操作对应了线段树上的一个区间加，可以发现上面的信息都是可以通过打 tag 解决的，并且 tag 支持合并，可以快速维护。在具体实现时，不需要开 $\frac{n}{C}$ 棵线段树，可以直接开一棵长度为 $n$ 的线段树，对应区间表示对应的小线段树即可。

对于整块的答案我们再开一个线段树，相邻整块的答案也可以用上面的做法类似求出，每次修改操作只会改变 $O(1)$ 个整块内的答案和，在线段树上修改即可。

所以整道题你只需要开三棵线段树，分别对应维护区间最大子段和的线段树，散块之间的线段树以及整块答案的线段树，总复杂度 $O((n+m)\log(n))$ 。

std 长度 6.25k ，写之前最好把细节先想好，想清楚三棵线段树具体在维护什么，想清楚后其实写起来也还行。很符合NOIP T4的风格

本题还有 $O((n+m)\sqrt{n})$ 的分块做法，写起来应该会比这三棵线段树好写，大家可以自行思考。