CF455E Function
Codeforces 分析 我们可以把题目中的过程看成二维网格上的游走，即每步可以向下或向右下走，代价为该列的权值，求从第一行走到 $(x, y)$ 的最短路。 注意到这样的最短路一定是先往下走若干步，然后往右下走到终点。因此设 $s$ 为 $a$ 的前缀和，那么从 $(1, i)$ 走到 $(x, y)$ 的最短路为 $s_y - s_i + a_i(x - y + i)$。我们要对每个询...
Codeforces 分析 我们可以把题目中的过程看成二维网格上的游走，即每步可以向下或向右下走，代价为该列的权值，求从第一行走到 $(x, y)$ 的最短路。 注意到这样的最短路一定是先往下走若干步，然后往右下走到终点。因此设 $s$ 为 $a$ 的前缀和，那么从 $(1, i)$ 走到 $(x, y)$ 的最短路为 $s_y - s_i + a_i(x - y + i)$。我们要对每个询...
Codeforces 分析 考虑一个好区间实际上是 $\max-\min=r-l$。 把所有询问按右端点排序，然后扫描线，则我们需要维护每个左端点到右端点的信息。 考虑每个左端点维护 $(\max-\min)-(r-l)$，显然这个东西是 $\geq 0$ 的，所以我们只需要维护最小值出现次数即可，可以用线段树维护。在右移右端点时需要更新信息，用单调栈维护最值即可。 但是我们要求的是所有区间...
Luogu LOJ 分析 因为 IP 地址可以看做长度为 $32$ 的二进制串，所以可以考虑用 Trie 树维护。 考虑查询。可以发现一个 IP 地址的匹配最大明确度是单增的，因此求出链上修改时间的单调栈即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-b...
Luogu 分析 首先有一个显然的性质：每一段左右端的贝壳大小一定相同，而且这一段的 $s_0$ 一定是左右端贝壳的大小。因为如果不是这样的话，我们显然可以把端点单独成一段，然后答案会变大。 设 $dp_i$ 表示前 $i$ 个贝壳最多可以得到多少柠檬，$c_i$ 表示 $i$ 是第几个 $a_i$ 大小的柠檬，容易得到状态转移方程 因为要求的是最大值，所以维护上凸壳；因为 $x_i$ 单...