自动搬运

查看原文

来自洛谷，原作者为

	Fucious_Yin 雨中做自己，云里成他人

搬运于2025-08-24 22:46:53，当前版本为作者最后更新于2024-08-05 14:49:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是 wqs 加广义笛卡尔树加斜率优化的 $O(n \log n)$ 题解，尾附 带注释代码。

欢迎收看，花子早早挂飞赶来上课，群友和我艰难保平差点迟到

先给链接：洛谷P9266 Nawiasowe podziały 和 loj3919 Nawiasowe podziały。

题意

定义一个括号序列的代价为，其是合法括号序列的子串的个数。

给定一个长为 $n$ 的括号序列，要求将其分成 $k$ 段，使得总代价最小。

$k \le n \le 1 \times 10^5$

题解

好像有很多什么诸如莫队或者 CDQ 的奇异一车 $\log$ 的做法，但花子手动把题加强到 $n \le 1 \times 10^6$，那么我们还是考虑单 $\log$ 做法。

括号序列先套路变成 +1-1 的序列，令前缀和为 $S_i$，看成一条折线。我们先考虑给一个区间 $[L + 1, R]$ 怎么去求代价。往折线上考虑，再回到序列上的形式化表示就是：

• $\sum_{L \le l < r \le R}{[S_l = S_r = \min_{i \in [l,r]}{S_i}]}$.

显然要求内部括号匹配且折线的最低点不爆。

因为这里有 $\min$，所以我们可以建出广义笛卡尔，同样的最小值同时提出来得到一棵多叉树，新建的方点代表管辖的区间，方点下挂圆点表示最小值位置，方点下方点代表子区间，区间之间顺序不变。这样就把序列问题转化到了树上。这个玩意是我用单调栈手搓出来的

考虑一个方点 $u$ 对一个分割出的区间 $[L + 1,R]$ 的贡献，令 $v_i$ 为下挂的第 $i$ 个圆点，就是 $\binom{\sum{[v_i \in [L,R]]}}{2}$。这里只用算在这个最小值上的贡献。

直观理解猜到答案关于 $k$ 是凸的，具体证明可以考察上面的贡献函数。最外层显然套一个 wqs，再把分成 $k$ 段转化为切 $k - 1$ 刀，那么我们只要考虑有切刀代价时的最优 $dp$ 即可，考虑在这个笛卡尔树上 $dp$。注意，这是一个双关键字的 dp，即要求在代价最小的前提下，切刀数最少，方便 wqs 判断。

还是从贡献函数上考虑，发现在 $u$ 这个点的贡献只与其下挂圆点的划分方式有关，也就是说，我们不关心他的一个儿子的子区间内究竟切了多少刀、切在哪里，只关心是否切刀。这样就好设计 dp 了。

设 $f_u$ 为 $u$ 子树内的至少切一刀最小代价。这样显然也无法转移，再设 $g_i$ 为 $u$ 的前 $i$ 个儿子的子树，第 $i$ 棵内一定切一刀的最小代价，这样每个 $g_i$ 加上后缀的代价贡献给 $f_u$。朴素的转移是枚举上一个吃刀的子树，计算之间的 $u$ 下挂圆点的代价，并加上中间子树内不切的代价，前者直接在这一层前缀和算，后者可以预处理再前缀和。

$sum_u$ 为 $u$ 子树内不切刀的代价，可以一遍 dfs 预处理。$prs_i$ 为当前节点 $u$ 的前 $i$ 个儿子子树不吃刀的代价和，$pre_i$ 为下挂圆点个数前缀合，$sons_u$ 为 $u$ 的儿子个数。则转移为：

• $g_i = \min_{j}(g_j + prs_i - prs_{j} + \binom{pre_i-pre_j}{2})$
• $f_u = \min_{i}(g_i + prs_{sons_u} - prs_i)$

直接做是 $O(n^2)$ 的，考虑优化。观察 $g$ 的转移式，发现同时关于 $i$ 和 $j$ 的项只有 $\binom{pre_i-pre_j}{2}$，令 $s_{i,j} = pre_i - pre_j$，也就是 $\frac{1}{2} \times (s_{i,j}^2 - s_{i,j})$，这是一个关于 $s$ 的极其优美的递增凸函数。同时又因为随着转移点 $j$ 的增大，$pre_j$ 也不降，那么每个转移点起始的斜率就不增，这就可以做我们经典的斜率优化，维护一个如上凸的函数图像，直接转移即可。建议手推推式子更清晰，这就是斜率优化的事情了，两个转移点的比较是可以 $O(1)$ 数学算的。

还有诸多细节，比如整棵树也可以不切，在根的时候得取个 $\min$；可以切在子树的缝隙里，儿子个数翻倍处理；还有 $pre_i$ 可能相同，那维护的图像中同样斜率的只能保留一条；还有由于是双关键字，哪怕几条线交在同一点也不能随便 pop，还要第二关键字比出内部偏序关系。

非常牛的一题啊。

我的代码喵