2025.9.26 测试

说好的蓝蓝紫紫呢……

矩阵

我直接和哈希做了。

正解是这样的，随机一个列向量 \(\mathbf{x}\) ，则如果 \(A\times B=C\) ，则 \(\mathbf x \times A \times B = \mathbf x \times C\) 。

列向量与方阵相乘是 \(O(n^2)\) 的。

这样判定的错误率是 \(\frac{1}{mod}\) 的（我也不知道为什么，反正很小）。

Code

长野原龙势流星群

据说本来是 Minkowski ，但是赛时被贪心爆标了。下面来介绍贪心。

当前树上权值最大的节点答案以及固定了，即其本身，因为加入任意一个点都不会使其更优。

如果其存在父亲，那么其一定在父亲的连通块内，因为这样不会使答案变劣，所以我们可以直接将其与父亲合并。

使用小根堆和并查集维护这个过程即可。复杂度 \(O(n\log n)\) 。

Code

序列与查询

注意 __int128。

我们发现询问对于一个子段的影响和其长度有关。

我们设 \(f_i\) 为长度为 \(i\) 的最大子段和，则 \(ans=\max\{f_i+x\cdot i\}\) 。

典型的斜率优化形式，求出 \((i, f_i)\) 的凸包，然后用斜率为 \(-x\) 的直线去切，切点即最优决策点。

现在我们的问题是求出 \(f_i\) ，\(O(n^2)\) 枚举听起来不太行。而现在我们面临一个需要处理所有子段的问题。

分治 。

将序列分成 \([l, mid]\) 和 \((mid, r]\) 两部分递归，然后处理之间的贡献。

即左侧距离 \(mid\) 长度为 \(i\) 的和是 \(L_i\) ，右侧同理定义 \(R_i\) 。

则 \(f_i=\max_j\{L_j+R_{i-j}\}\) ，这是一个 Minkowski 和的形式。

同时发现，最后我们要求的就是凸包，不在目前凸包上的一定不需要，所以直接 Minkowski 合并即可。

同时发现我们只需要求 \(f_i\) ，最后再统一求一次凸包就好了，不需要合并凸包。

Code

Hills and Pits

先假定 \(l=1,r=n\) ，且 \(s<t\) 。记 \(\{a\}\) 前缀和 \(sum\) 。

总和 \(<0\) 不合法，先判掉。

然后路径就变成了这样：

发现 \(s\rightarrow t\) 的这一段是可以折返的，而折返就意味着遇到一段 \(sum<0\) ，然后在之后的第一个 \(sum\ge 0\) ，折返回去填平。

也就意味着，\(sum>0\) 可以少走一遍， \(sum<0\) 需要多走一遍，我们想要确定一个子段 \(s\rightarrow t\) 使得这样的情况最优。

我们定 \(sum\ge0\) 权值为 \(1\) ，\(sum<0\) 权值为 \(-1\) ，问题就是求 \([1, n)\) 最大子段和。

同时发现，左端点一定是 \(1\) ，这也满足了我们最初那张图的限制。

现在问题搬到了区间上，则 \(sum\ge sum_{l-1}\) 权值为 \(1\) ，\(sum<sum_{l-1}\) 权值为 \(-1\) 。

根据值域扫描线，需要支持单点修改，区间查询最大子段和，这不就 小白逛公园 。

然后再倒过来做一遍就好了。

Code