做题记录

fzitb7912 · 2024-10-29 18:40:50 · 个人记录

• [ ] 以后写的题基本上都会写题解的，不然忘了就是抄的了。

P2519

我们将所有人按照成绩排序。那么对于一个有 a_i 个人比他低，b_i 个人比他高的情况，可以看作对于区间 [a_i+1,n-b_i]，里面任意一个 j，都有 val_i=val_j。然后问题就变成了：选出若干个不相交的区间，使得选出区间数量最大。

我们记 cnt_{l,r} 表示 a_i+1=l\land n-b_i=r 的 i 的数量，若 cnt_{l,r}> r-l+1，那么至少有 cnt_{l,r}-(r-l+1) 个人说假话。同时，a_i+1 > n-b_i 的人也一定说假话。把这些排除之后，我们将 cnt_{l_i,r_i} 看作区间 [l_i,r_i] 的权值。那么直接 DP 就可以了。定义状态函数 f_{i} 表示前 i 个区间的最大价值，那么有：f_i=\max (f_j| r_j < l_i)+cnt_{l_i,r_i}。答案就是 \max\limits_{i=1}^{m} f_i。双指针求前缀 \max 可以做到 O(n) DP，但是要排序。时间复杂度 O(n\log n)。

P7706

考虑线段树。对于区间上传的时候，我们有 4 种情况：

1. 最大值在左儿子。
2. 最大值在右儿子。

那么，我们直接维护：区间答案，区间 a_i-b_j 最大值，区间 -b_j+a_k 最大值，区间 a_i 最大值，区间 b_i 最小值就行了。时间复杂度 O(n\log n)。

P3215

考虑一个括号序列的最小操作次数是多少。记 a 为前缀 ( 的数量减去 ) 的数量的最大值，b 为后缀最小值。那么有操作次数为：\lceil \frac{a}{2} \rceil+\lceil \frac{-b}{2} \rceil。证明不难，考虑将相邻 )) 变成 ()，然后优化一下。

然后就很简单了。这里有一个很强的 trick。不难发现，不管是区间翻转还是区间反转，它们都只有常数种状态。那么只要我们能够先维护出这些状态的值，那么就能 O(1) 操作了。

记 pmax 为前缀最大值，pmin 为前缀最小值。smax 和 smin 同理。

对于区间覆盖操作，直接做就行了。

对于区间翻转操作，前后缀交换即可。

对于区间反转，因为左右括号互换，所以 pmin 将会变成 -pmax，pmax 变成 -pmin。后缀同理。

然后直接用文艺平衡树维护就行了。时间复杂度 O(n\log n)。

P7739

咕一下。trick 和 P3215 相同。发现标记种类数只有常数个就能维护了。

我畏黑。

CF997E

考虑离线。我们枚举 r，记 f_l 为对于当前的 r，[l,r] 的所有子区间的贡献。那么 r 每次 +1，max\ne a_r\land min \ne a_r 的 l 的贡献都不变，相当于复制一遍。然后 max = a_r \lor min=a_r 的 l，我们能过维护出其变化量。同时，r+1 时，全局最小值 -1。由于 max-min-r+l \ge 0，所以我们只需要维护出最小值，最小值数量。当最小值为 0 时，有贡献为其出现次数。使用线段树可以做到 O(n\log n)。给 7 秒是真的嘛。

P9990

lxl 讲课说的比较抽象。没学过扫描线，弱爆了。鉴定为扫描线模板题。

考虑扫描线。对于 r 移动到 r+1，记 pre_i 为最大的 j(j<i)，使得 a_j=a_i。那么对于 [pre_r+1,r] 的所有 l，其区间出现过的数的个数都会较 [l,r-1] 多 1。因为这题只考虑奇偶性，所以可以看作其奇偶性异或了 1。那么答案就是奇偶性为 1 的子区间的数量。

像这种题，我们可以将子区间 [l,r'] 看作区间 [l,r] 的前缀。只要我们扫描 r，我们就能在每个 l 上面维护所有 r\ge l 的前缀的答案了。记 f_l 为 l 的答案。则 [l,r] 的所有子区间的答案就是 \sum\limits_{l'=l}^{r} f_{l'}。

那么这题就很简单了吧。不难发现，只有 [pre_r+1,r] 的前缀较 r-1 异或了 1，其余的相当于是复制一遍。因为要查询的是所有历史的前缀的和，我们记为 sum。又记 cnt_0 为前缀为 0 的数量，cnt_1 同理。那么 [pre_r+1,r] 的 cnt_0 与 cnt_1 将会交换。然后 sum 增加量就为 [1,r] 的 cnt_1。

这里有个 trick，就是像这种维护区间历史和的问题，通常可以用矩阵运算。形式化的，我们有：

对于异或操作：\begin{bmatrix}cnt_0 &cnt_1&sum\end{bmatrix} \times \begin{bmatrix}0 & 1 & 0 \\ 1 & 0 & 0\\0 & 0 & 1\end{bmatrix}。

对于更新历史和操作：\begin{bmatrix}cnt_0 &cnt_1&sum\end{bmatrix} \times \begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 1\\0 & 0 & 1\end{bmatrix}。

使用线段树与矩阵可以做到 O(a^3n \log n) 的复杂度。

然后你会发现这题矩阵乘法过不了（如果不会卡常）。考虑正常懒标记。记 tag1 表示区间翻转懒标记，tag2 表示区间更新历史和的懒标记。实际上就是 CF997E 的做法，直接写上去就行了。时间复杂度 O(n\log n)。

注意懒标记下传的先后顺序，不然调很久。然后这题有个双倍经验，P10822。

P8868

题目抽象。相当于是对于每组 l,r，求 [l,r] 的所有子区间 [l',r'] 的 \max(a_i)\times \max(b_i) 的和。那这就是 CF993E 的 pro max 版了。

考虑扫描线。对于 r 到 r+1 时，[l_r,r] 的最大 a_i 值都会变成 a_r，[L_r,r] 的最大 b_i 值都会变成 b_r。不难发现，其它的相当于是复制 r-1。现在考虑变化量：\sum (x_i+a)(y_i+b)=\sum x_iy_i + \sum x_ib+\sum y_ia +\sum ab。那么我们只需要维护最大值相乘的答案，a 最大值的和，b 最大值的和，区间长度这些值就行了。时间复杂度 O(n\log n)。

注意到线段树直接写很难。考虑使用矩阵。这题和 P9990 实现了矩阵与普通懒标记之间的转化，需要视题目而定。现在我们构造出矩阵 \begin{bmatrix}sab&sa&sb&len & sum\end{bmatrix}。那么有以下几种标记的维护：

1. 区间 a_i 加 x。则：\begin{bmatrix}sab&sa&sb&len&sum \end{bmatrix} \times \begin{bmatrix}1 &0&0&0&0\\0&1&0&0&0\\x&0&1&0&0\\0&x&0&1&0\\0&0&0&0&1\end{bmatrix}。

2. 区间 b_i 加 x。则：\begin{bmatrix}sab&sa&sb&len &sum\end{bmatrix} \times \begin{bmatrix}1&0&0&0&0\\x&1&0&0&0\\0&0&1&0&0\\0&0&x&1&0\\0&0&0&0&1\end{bmatrix}。

3. 区间更新历史和。则：\begin{bmatrix}sab&sa&sb&len &sum\end{bmatrix} \times \begin{bmatrix}1&0&0&0&1\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\end{bmatrix}。

然后就能在 O(a^3 n \log n) 的复杂度解决了。好，不难发现，这个被卡了。复杂度明显不对。但是可以卡常。

CF868F

纯唐氏题。

观察到 k \le 20，猜测复杂度为 O(kn) 乘一些东西。然而没用。

很显然，对于一个值 x，其价值为 \frac{cnt_x \times (cnt_x-1)}{2}。很显然，这玩意满足决策单调性。证明如下：

记 w(l,r) 为区间 [l,r] 的价值。对 a_l,a_r 进行分类讨论：

2. 所以有：$w(l,r)+w(l+1,r-1)\ge w(l+1,r)+w(l,r-1)$，满足四边形不等式。所以原问题具有决策点单调性。

然后就是板子了。我们一层一层地 DP。每层使用分治决策点可以做到 O(kn\log n)。具体地，见 CF321E的题解。

P3863

扫描线练手题。

注意到我们每次修改操作直接将 [l,r] 的数修改很难。而对于一次在时间 t 的修改操作 x，实际上相当于给时间 [t,m] 的每一个值都增加了 x。形式化地，我们记 d_{i,j} 表示时间 i 时第 j 个数的增加量，则该时间 a_j 就应该变成 a_j+d_{i,j}。

考虑扫描线。我们建立平面直角坐标系，以下标为纵坐标，时间为横坐标。则一次修改操作可以转化成将左上角坐标为 (l,m)，右下角坐标为 (r,t) 的矩形中所有点增加了 x。则一次查询就相当于是查左上角坐标为 (p,t) 右下角坐标为 (p,0) 的矩形中，有多少个数不小于 y-a_{p}。使用分块维护可以做到 O(n\sqrt{n}\log{\sqrt{n}}) 的复杂度。

P7560

P8512

CF407E

AT_joisc2019_j

简单的吧。对于选出来的 k 个数，前面的值一定，根据绝对值的几何意义，显然后面的按照 c_{k_ i} 排序最优。虽然翻译没说，但是可以给 k_i 重排。记 k 为按照 c_i 从小到大排序后的结果，则有价值为：\sum\limits_{i=1}^{m} v_{k_i}-2(c_{k_m}-c_{k_1})。

将原序列按照 c_i 排序，定义状态函数 f_{i,j} 表示前 i 个数，选 j 个数的最大价值。则有转移方程：f_{i,j}=\max(f_{k,j-1}+2c_{k})-2c_{i}+v_i。

发现这种方式难以维护。注意到，k_2\sim k_{m-1} 实际上是选了 (k_1,k_m) 中前 m-2 大的 v_i 的下标。所以定义状态函数 f_i 表示 k_m=i 时的最大价值。那么有：f_{i}=\max(v_j+2c_j+w(j+1,i)|1 \le j \le i-m+1)+v_i-2c_i。其中 w(l,r) 为区间 [l,r] 前 m-2 大的 v_i 的和。

注意到，w(l,r) 明显满足决策单调性。证明如下：

1. 若 a_l 在 w(l,r) 中被选且 a_r 在 w(l,r) 中被选。记 x,y 为去掉 a_l,a_r 后替代的值。则：w(l,r)+w(l+1,r-1)=2w(l,r)-a_l-a_r+x+y，w(l+1,r)+w(l,r-1)=2w(l,r)-a_l-a_r+x+y。故 w(l,r)+w(l+1,r-1)=w(l+1,r)+w(l,r-1)。
2. 若 a_l 在 w(l,r) 中被选。记 x 为去掉 a_l 后替代的值。则：w(l,r)+w(l+1,r-1)=2w(l,r)-a_l+x，w(l+1,r)+w(l,r-1)=2w(l,r)-a_l+x。故 w(l,r)+w(l+1,r-1)=w(l+1,r)+w(l,r-1)。
3. 若 a_r 在 w(l,r) 中被选。记 x 为去掉 a_r 后替代的值。则：w(l,r)+w(l+1,r-1)=2w(l,r)-a_r+x，w(l+1,r)+w(l,r-1)=2w(l,r)-a_r+x。故 w(l,r)+w(l+1,r-1)=w(l+1,r)+w(l,r-1)。
4. 若都没选，则 w(l,r)+w(l+1,r-1)=w(l+1,r)+w(l,r-1)。

所以 w(l,r)+w(l+1,r-1)=w(l+1,r)+w(l,r-1)，满足决策单调性。然后直接分治使用主席树维护能够做到 O(n\log^2 n)。

CF1777F

考虑分治。

对于经过中点的情况，以最大值在左边为例。我们有价值为：mx_l⊕a_l⊕\dots ⊕ a_{mid}⊕a_{mid+1}⊕\dots⊕a_r。记 s_i 为后缀异或和，p_i 为前缀异或和。则有：mx_r ⊕ s_l ⊕ s_r。不难发现，mx_l ⊕ s_l 为定值，求一个最大异或对就行了。另一种情况同理。使用 Trie 可以做到 O(n\log ^2 n)。

P8511

考虑观察点 x 的答案长什么样。记 a,b 为原树上的最大异或对。若 x 不是 a 的祖先也不是 b 的祖先，那么一定可以让 v_a 和 v_b 异或起来，且是最大的。而是 a 的祖先的点集形成了一条链，b 的同理。那么我们再暴力给这些点找答案就是对的了。形式化的，我们从上往下找，当一个点 u 的儿子 v 是 a 的祖先，则 u 的其它儿子为根的子树都可以被算进答案，先它们把答案算出来之后再传到 v 就行了。b 的方式同理。使用 trie 维护可以做到 O(n\log V) 的时间复杂度。

P6072

P8511 的双倍经验属于是。对原树进行前缀异或和，那么问题转化为：

求一对子树内的最大异或对与子树外的最大异或对，使得它们加起来最大。

很显然，子树外的答案就是 P8511，子树内的可以通过启发式合并做到 O(n\log n \log V)。所以总的时间复杂度为 O(n\log n\log V)。

P4689

考虑对于以 R 为根时 x 为根的子树长什么样。很显然，当 R 不是 x 在以 1 为根的子树中的节点时，x 为根子树形态不变，否则为除了离 x 最近的点（是 R 的祖先）为根子树外的其它所有节点。

不难发现，一个 x 为根的子树在根不确定的情况下最多拆成 2 个连续的区间。那么问题就变成了给定 2\sim 4 个区间，求它们 a_i=a_j 的数量。

对于这个问题，问题有 4 个自由度，显然很难在正确的复杂度内完成。考虑使用差分降低问题的自由度。形式化的，将一个区间 [l,r] 变成 [1,l-1] 和 [1,r] 两个前缀，那么问题就只有 2 个自由度了，因为左端点已经固定。那么直接差分然后莫队就能得到答案了。时间复杂度 O(n\sqrt{m})。

P5386

难写。

经典 trick 题。

不难发现，直接做相当于在维护一个有 4 个自由度的问题。考虑用莫队维护其中一些，剩下的自由度由某些其它的东西维护。

发现用莫队维护区间不好做，那么考虑维护值域。如果我们用回滚莫队做到不删除，将当前区间中的点看做 1，其余的看作 0。则只需要维护出每个连续 1 的段的长度平方和就行了。因为我们不删，所以只需要考虑合并的问题。用线段树维护可以做到 O(n\sqrt{n}\log n)。

复杂度明显不够优秀。不难发现，一个点加进来后能与其它点合并当且仅当与它相邻的点也被加进来了，所以直接用链表就足够了。对于每个连续的 1，我们在其最左边存下平方和。然后对链表进行分块。很显然的，查询区间 [l,r] 的答案时，最多只会有 2 个散块的答案维护错误。直接暴力求它们的答案就行了。则修改复杂度为 O(1)，单次询问复杂度为 O(\sqrt{n})。故总的时间复杂度为 O(n\sqrt{n})。

P5047

P7448

P6779

P7882

P7446

考虑没有修改的时候要怎么做。

不难发现，这就是弹飞绵羊了。对序列分块，对于每个位置 x，记 p_x 为第一次跳出当前块时会落在哪里。那么两个点 x,y 的 \operatorname{LCA} 就可以通过一直跳到相邻的块，直到两个点在同一个块内且 p_x=p_y 为止。然后暴力地一步一步跳。不难发现，因为一共 \frac{n}{B} 个块，所以跳相邻的块的步数不超过 \frac{n}{B}。而块内暴力跳最多跳 B 步。所以当 B=\sqrt{n} 的时候我们就能在 O(\sqrt{n}) 的时间复杂度内求出 \operatorname{LCA} 了。

现在考虑修改。发现 a_x 只减不加。那么对于 a_x 与 x 不在一个块的时候，p_x 很显然就是 a_x。如果在同一个块，我们对这个块暴力重构，则最多会重构 n 次，因为每个点最多修改 \sqrt{n} 次就变成上面的那种情况了。所以这样暴力重构均摊复杂度是 O(\sqrt{n}) 的。

所以该算法的时间复杂度为 O(n\sqrt{n})。

P3591

考虑根号分治。对于 k \ge B 的情况，我们可以暴力往 \operatorname{LCA} 跳，最多跳 \frac{n}{B} 步。用长剖求树上 k 级祖先可以做到 O(n\log n+\frac{n^2}{B})。对于 k<B 的情况，我们暴力处理 f_{i,x} 表示从 i 开始往上一直跳，每次跳 x 步，最后跳到深度最小的点时经过的点权和。那么我们只需要找到距离 \operatorname{LCA} 最近的一个深度与 u 关于 k 同余的点，差分一下即可。时间复杂度 O(nB+n\log n)。平衡一下当 B=\sqrt{n} 时可以做到 O(n\log n+n\sqrt{n})。

P7967

这题只有蓝？？？这也许是我目前写的最长的蓝题题解了。

注意到，对于相邻两个位置的磁铁 p_i,p_{i+1}。只有当 x_{p_{i+1}}-x_{p_i} \ge \max(r_{p_i},r_{p_{i+1}}) 时两个磁铁才不会相互吸引。

我们把一个磁铁的排列状态极致压缩，保证 x_{p_{i+1}}-x_{p_i} = \max(r_{p_i},r_{p_{i+1}})。记这样会占用 k 个位置，那么剩下的 l-k 个位置就可以在这些磁铁之间随便插了。方案数为 C_{l-k}^{n}。那么现在我们就只需要维护出在占用 k 个位置时，极致压缩后磁铁排列的方案数。

不妨将 r_i 从小到大排序，那么将 i 插到 x,y 之间时，代价一定是 r_i。这样我们就去掉了 \max(r_{p_i},r_{p_{i+1}}) 的限制。

考虑 DP。不难发现，对于第 i 个磁铁，如果我们放到前 i-1 个磁铁形成的排列的两端，则会产生 r_i 的代价。如果我们插到 x 和 y 之间，则会产生 r_i-\max(r_x,r_y) 的代价。前者维护不难，考虑如何维护后者。

这里有个很简单的做法，貌似叫连续段 DP。因为我们插中间会破坏掉原来的结构，那干脆让之前就没有这个结构。形式化的，我们将前 i-1 个磁铁分成若干个连续的段，那么 i 插到 x,y 之间就相当于是合并了两个连续段。只要我们强制让已经合并的两个磁铁之间不再有磁铁插入，就能够保证算法的正确性了。因为这个过程相当于是在倒着维护插入的过程，每次后插入的磁铁合并相邻的磁铁后，前面插入的磁铁就不可能再去破坏了。

定义状态函数 f_{i,j,k} 表示前 i 个磁铁，已经形成了 j 个连续段，且极致压缩后占用了 k 个位置的方案数。对第 i 个磁铁进行分类讨论：

1. 单独形成一个连续段，有：f_{i,j,k}\to f_{i,j,k}+f_{i-1,j-1,k}。
2. 拼在某个连续段的两边，有：f_{i,j,k}\to f_{i,j,k}+2\times j\times f_{i-1,j,k-r_i}。
3. 将两个连续段拼起来。因为 r_i 是目前最大的，所以拼起来的代价将会是 2\times r_i。有：f_{i,j,k}\to f_{i,j,k}+2\times C_{j+1}^2 \times f_{i-1,j+1,k-2\times r_i}。

那么答案就是 \sum\limits_{i=0}^{l-n} f_{n,1,i}\times C_{l-i}^{n}。时间复杂度 O(n^2l)。

P10761

考虑 DP。定义状态函数 f_{i} 表示到 i 的方案数。则有：f_i=\sum\limits_{j=1}^{i-1} f_j[(i-j)\bmod b_j=0]。

对于这种无脑跳 d_i 步的题面，不难想到根号分治。使用刷表的方式更新状态函数。对于 d_i\ge B 的点，因为能过转移的点最多有 \frac{n}{B} 个点，所以暴力转移就行了。对于 d_i<B 的点，可以给它打个标记，tag_{i,j} 表示 b_x=i 且 x\bmod b_x =j 的所有 f_x 的和。因为当 i 与 j 的差同余 b_j 时都能转移。所以这样是可行的。由于 b_i<B，所以模数也不超过 B。每次转移的时候暴力枚举 b_x 就行了。单次转移的复杂度是 O(B) 的。所以总的复杂度 O(nB+\frac{n^2}{B})。B 取 \sqrt{n} 最优。

对于 x 的限制，搞一个差分就行了。

CF1746F

考虑莫队。不难发现时间复杂度炸裂。

考虑乱搞。如果区间 [l,r] 中任意一个 k|cnt_x，则满足条件。那么很显然的有：k|\sum cnt_x\land k|cntx\times x。如果我们 k|\sum a_i，但不满足 k|cnt_x，则一定有 k|x。而这种情况的概率是 \frac{1}{k}。因为一旦有 1 个 x 不满足就全不满足。

那么如果我们给 x 一共 m 个哈希值。则这种情况下错误的概率就变成 \frac{1}{k^m} 了。因为 k\ge 2 才可能不满足条件，所以当 m\ge 32 时这个概率就极小了。时间复杂度 O(Vn\log n)。

实测 V=25 就能过了。

CF696E

P5314

P9607

典。不如 normal。

这里有个简单的性质：前缀/后缀的 \gcd 值的种类数最多 \log V 个。证明简单吧，相邻两个 \gcd 至少是 \frac{1}{2}。

然后就没了。考虑分治。对于每个 l，求一个 i。使得 mid<r \le i 都满足：\max\limits_{j=mid+1}^{r} a_j \le \max\limits_{j=l}^{mid} a_j。那么此时 \max 值已经固定了，暴力枚举 (mid,i] 里面的 \gcd 值就行了。对于 r>i 的情况，因为有 \gcd 不好直接搞。所以再枚举 r 弄一下 l 就行了。时间复杂度 O(n\log n\log V)。

P3515

困难。

转化一下式子：

因为我们要找最小的非负整数 p，所以有：p=\max(0,\max(a_j+\sqrt{|i-j|})-a_i)。那么我们只需要维护 \max(a_j+\sqrt{|i-j|}) 就行了。因为是取 \max，所以 j \le i 和 j>i 可以分开求。以 j \le i 为例。

我们有：g_i=\max(a_j+\sqrt{i-j})。不难想到可能有决策单调性。记 w(l,r)=a_l+\sqrt{r-l}。则 g_i=\max(0+w(j,i))。那么有：

因为 \sqrt{x}-\sqrt{x-1} > \sqrt{x-1}-\sqrt{x-2}。所以原式的值大于 0。

然后就分治跑就行了。时间复杂度 O(n\log n)。有三倍经验。

P6246

考虑 DP。定义状态函数 f_{i,j} 表示前 i 个数，分成 j 段的方案数。记 w(l,r) 表示在 [l,r] 里放一个邮局且 [l,r] 中所有人都去的最小代价。 那么有：f_{i,j}=\max(f_{k,j-1}+w(k+1,i))。

现在考虑 w(l,r) 怎么求。不难发现，当邮局取 \frac{l+r}{2} 时是最优的。那么 w(l,r) 就可以转移了，有：w(l,r)=w(l,r-1)+a_r-a_{\lfloor \frac{l+r}{2}\rfloor}。猜测具有决策单调性。开始证明：

所以 w(l,r)+w(l+1,r-1)=w(l,r-1)+w(l+1,r)，具有决策单调性。

然后就能 wqs 二分了。定义新的状态函数 f_i 表示前 i 个的答案。那么有：f_i=\min\{s_i-s_j-(i-j)a_j+\min\{(j-k)a_j-s_j+s_k+f_k|0\le k <j\}|1\le j \le i\}-mid。

简化一下，有：f_i=\min\{s_i-ia_j-2s_j+2ja_j+\min\{(-ka_j+s_k+f_k|0\le k <j\}|1\le j \le i\}-mid。

记 g_i=\min\{f_j+s_j-ja_i|0 \le j<i\}。那么 f_i=\min\{s_i-2s_j-ia_j+2ja_j+g_j|1 \le j \le i\}-mid。

然后会发现它们都可以斜率优化，直接维护即可。时间复杂度 O(n\log V)。

P5308

一眼了吧。

发现每轮的情况不在意具体是哪个人，那么直接定义状态函数 f_{i,j} 表示前 i 轮结束，还剩 j 个人的最大价值。那么有转移方程：f_{i,j}=\max\{f_{i-1,k}+\frac{k-j}{k}| j \le k \le n\}。因为最后剩了 0 个人，而这玩意又很能抽象。那么就抽象一下问题：将序列分成 k 段，若第 i 段是 [l,r]，则价值为 \frac{r-l}{r}。

然后就有：f_{i,j}=\max\{f_{i-1,k}+w(k,j)|0 \le k \le j\}。其中 w(l,r)=\frac{r-l}{r}。然后这玩意明显有决策单调性，懒得证了。使用 wqs 二分可以做到 O(n\log V)。

我们有转移方程：f_{i}=\max(f_{j}+1-\frac{1}{i}\times j)-mid。可以使用斜率优化做到 O(n)。

P6173

考虑 DP。

首先破环成链。定义状态函数 f_{i,j} 表示前 i 个房间解锁了 j 个门的最小代价。那么有：f_{i,j}=\min(f_{k,j-1}+\sum\limits_{w=k+1}^{i}r_w\times (w-k-1))。不难发现，我们对每个 i 都加上了 r_i\times (i-1)，这是定值。所以转移方程可以写成 f_{i,j}=\min(f_{k,j-1}+k \times s_k-k \times s_i)。其中 s_i=\sum\limits_{j=1}^{i}r_j。

因为 k \le 7，所以我们去枚举起点，使用斜率优化就能做到 O(n^2k) 了。

P5574

我们需要将序列分成 k 段，使得每段的顺序对数量和最小。考虑 DP。定义状态函数 f_{i,j} 表示前 i 个数分成 j 段的最小代价和。那么有：f_{i,j}=\min(f_{k,j-1}+w(k+1,i))。其中 w(l,r) 表示区间 [l,r] 的顺序对数量。

注意到，w(l,r) 具有决策单调性。我们记 x 为比 a_l 大的数的数量，y 为比 a_r 小的数的数量。那么有：