ABC234

G

赛时：想出正解，未能实现

设 \(f[i]\) 为前 \(i\) 个元素的权值和，则有 \(f[i]=\sum_{j=1}^{i}f[j-1](\max_{k=j}^{i}\{A_{k}\}-\min_{k=j}^{i}\{A_{k}\})\)，可以将 \(\max\) 与 \(\min\) 分别求和

后缀 \(\max\) 相同的一段可以合并计算，且从 \(i-1\) 变到 \(i\) 时改变的一定是一段后缀，可以用单调栈维护，记录 \(\max\) 和 \(\sum f\)，再用变量记录栈内的 \(\sum\max\times f\)，进出栈时更新即可

code

Ex

赛时：KDT 通过。（赛后发现了 200ms KDT，令我大为震惊）

以下是官方题解做法

把每个点 \((x,y)\) 分配到 \(\text{Packet}(\lfloor\frac{x}{k}\rfloor,\lfloor\frac{y}{k}\rfloor)\)，显然与 \(\text{Packet}(x,y)\) 中点构成合法点对的点，一定在其周围 \(8\) 个 \(\text{Packet}\) 中，暴力即可，时间复杂度 \(O(n+m)\)。

证明：

记 \(f(n)\) 为一个大小为 \(n\) 的 \(\text{Packet}\)，至少有多少个合法点对满足其两点均在该 \(\text{Packet}\) 中。将一个 \(\text{Packet}\) 分为 \(4\) 个 \(\frac{k}{\sqrt{2}}\times\frac{k}{\sqrt{2}}\) 的正方形，则一个正方形内的任两点都是合法点对，且至少有一个正方形内点数 \(\ge\frac{n}{4}\)，因此 \(f(n)=\Omega(n^{2})\)

由 \(\sum_{x,y}f(|\text{Packet}(x,y)|)\le M\) 可得 \(\sum_{x,y}|\text{Packet}(x,y)|^{2}=O(n+m)\)。算法中我们枚举的点对数为 \(\sum_{x,y}\sum_{d_{1}=0}^{1}\sum_{d_{2}=0}^{1}|\text{Packet}(x,y)||\text{Packet}(x+d_{1},y+d_{2})|\)，且有 \(ab\le\frac{a^{2}+b^{2}}{2}\)，因此也为 \(O(n+m)\)

另有人类的智慧做法，随机化后快速估计一下复杂度的思想很值得借鉴