\(9.1\)

鸽。

\(9.2\)

模拟赛。

难度大概是 \([2300,2400]+[2900,3300]+?\)。

• \(\text{A}\)：

给定一个正整数序列 \(\{a_n\}\)，和一个初始全 \(0\) 的整数序列 \(\{b_n\}\)，每单位时间 \(\forall i\in [1,n],b_i\gets b_i+1\)。
定义对于 \(b_j\) 的一次操作为：操作后该 \(b_j\) 不再执行 \(b_j\gets b_j+1\) 操作。
求一个最大的 \(k\) 满足：可以每隔 \(k\) 单位时间做若干次个 \(b_i\) 进行操作，使得最终 \(b_i\ge a_i\) 且 \(\sum\limits_{i=1}^n b_i-a_i<m\)。
\(n\le100,a_i\le10^9,m\le10^{11}\)。

显然我们对于 \(a_i\) 要求不小于 \(a_i\) 的最小的 \(b_i\)，易得 \(b_i=\lceil \frac{a_i}{k}\rceil\Rightarrow b_i-a_i=(-a_i)\bmod{k}\)。

即题目转换为求最大的 \(k\) 使得 \(\sum\limits_{i=1}^m ((-a_i)\bmod{k})<m\)。

考虑单调性，但这个柿子显然没有单调性。

考虑为什么没有单调性，\(a=bq+r\Rightarrow r=a-bq\)，由于 \(a\) 均为常数，所以 \(r\) 的值由 \(bq\) 决定，\(bq=\lfloor \frac{a}{b}\rfloor b\)。设 \(b'>b\)，则当 \(\lfloor \frac{a}{b}\rfloor=\lfloor \frac{a}{b'}\rfloor\) 时 \(b'q>bq\Rightarrow r'<r\)。也就是说，当 \(\lfloor \frac{a}{b}\rfloor\) 相同时，\(a\bmod{b}\) 具有单调性。

考虑整除分块，对于 \(a\)，其 \(\lfloor \frac{a}{b}\rfloor\) 的值至多只有 \(\sqrt{a}\) 个。

则我们对于每个 \(a_i\) 做一个整除分块（，然后把所有使得 \(\lfloor \frac{a_i}{b}\rfloor\) 不同的 \(b\) 丢到一个 vector 里面，然后排个序去个重，对于所有的 \(k\in [t_i,t_{i+1}]\) 原式具有单调性，二分即可。

这样子看起来 vector 的大小为 \(\Theta(n\sqrt{V})\)，实则并不然，myee 说 vector 的大小为 \(\Theta(\sqrt{nV})\)，具体来说是 \(\le\sqrt{nV}\) 的显然至多有 \(\sqrt{nV}\) 个，而 \(\ge\sqrt{nV}\) 的至多会有 \(\frac{V}{\sqrt{nV}}=\sqrt{nV}\) 个。

二分的 check 函数如果一个个累加的话，复杂度为 \(\Theta(n\sqrt{nV}\log V)\)，能不能跑过去看 rp。

我们考虑优化这个二分的 check，我们考虑维护每次 \(\sum\limits_{i=1}^m ((-a_i)\bmod{k})<m\) 变化的值，分两种：

1. 块内相邻两值之差显然是等差数列，考虑维护该公差。
2. 相邻两块边界的差。

具体维护大分讨，我也没有搞清楚。

通过维护公差，我们可以用小学奥数 \(\Theta(1)\) 计算出对应的 \(k\) 的值。

最终复杂度 \(\Theta(n+\sqrt{nV})\)。

• \(\text{B}\)：

给定一个正整数环 \(\{a_n\}\)，把其划分成 \(k\) 区间 \(\{S_k\}\)，求 \(\max \{\sum\limits_{i=1}^k \sqrt{\sum\limits_{j\in S_i} a_j}\}\)。
\(k\le n\le 1500,a_i\le 10^9\)。

Too Hard。

• \(\text{C}\)：

https://loj.ac/p/3073。

Too Hard。

杂题选做

• \(\text{CF1725L}\)：

难度 \(2400\)。

https://codeforces.com/problemset/problem/1725/L。
给定一个整数序列 \(\{a_n\}\)，我们定义一次操作为：
1.\(a_{i-1}\gets a_{i-1}+a_i\)。
2.\(a_{i+1}\gets a_{i+1}+a_i\)。
3.\(a_{i}\gets -a_i\)。
求最少操作数使得 \(\forall a_i\ge 0\)。
\(n\le 10^5\)，\(-10^9\le a_i\le 10^9\)。

人类智慧题。

注意到操作后全局和不变，故考虑前缀和。设 \(s_i=\sum\limits_{j=1}^i a_j\)，则原操作等价于交换 \(s_{i-1},s_i\)。

由于 \(a_i=s_i-s_{i-1}\) 所以 \(a_i\ge 0\) 等价于 \(s_i\ge s_{i-1}\)。

那么题目就变为了每次考虑交换 \(s_{i-1}\) 和 \(s_i\)，求最少操作次数使得 \(\{s_n\}\) 单调不降，答案显然是 \(\{s_n\}\) 的逆序对数。

再考虑无解的条件。

由于 \(i\in [2,n-1]\)，所以 \(s_n\) 无法和 \(s_{n-1}\) 交换，故当 \(\exists i\in [1,n-1]\) 使得 \(s_i>s_n\) 时无解。

然后当存在一个 \(s_i<0\) 时，显然 \(s_i\) 必须排到首位，但由于 \(a_1=s_1<0\)，所以同样无解。

• \(\text{CF1609E}\)：

难度 \(2400\)。

https://codeforces.com/contest/1609/problem/E。
给定一个长为 \(n\) 的字符串 \(s\)。
有 \(q\) 次修改，每次为 \(s_p\gets c\)。
定义一次操作为令 \(s_k\gets c'\)，对于每次修改后输出最少修改几个位置可以使得 \(s\) 中不存在子序列 abc。
\(n,q\le 10^5\)，\(s_i,c\in\) a,b,c。

小清新线段树。

考虑维护 \(6\) 个值：\(a,b,c\) 的个数 \(cnt_a,cnt_b,cnt_c\) 和最少的修改位置数使得区间中不存在子序列 ab，bc 和 abc 的 \(f_{ab},f_{bc},f_{abc}\)。

易得 \(fa_{cnt_a}=ls_{cnt_a}+rs_{cnt_a}\)，同理有 \(fa_{cnt_b}=ls_{cnt_b}+rs_{cnt_b}\) 和 \(fa_{cnt_c}=ls_{cnt_c}+rs_{cnt_c}\)。

同时有 \(f_{ab}=\min\{ls_{cnt_a}+rs_{f_{ab}},ls_{f_{ab}}+rs_{cnt_b}\}\)，同理有 \(f_{bc}=\min\{ls_{cnt_b}+rs_{f_{bc}},ls_{f_{bc}}+rs_{cnt_c}\}\)。

同样可以得到的是 \(f_{abc}=\min\{ls_{cnt_a}+rs_{f_{abc}},ls_{f_{abc}}+rs_{cnt_c},ls_{f_{ab}}+rs_{f_{bc}}\}\)。

然后线段树随便维护一下即可，复杂度 \(\Theta((n+q)\log n)\)。