乱做的杂题总结

· · 个人记录

AT

AGC001E

远古AGC，但题目质量依然很高。

形式化题面：

有 n 个数对 (a_i,b_i) 求出下面式子对 10^9+7 取模的值。

\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \binom{a_i+b_i+a_j+b_j}{a_i+a_j} n \le 2\times 10^5， a_i,b_i\le 2\times 10^3

一看上去就感觉是非常经典的拆式子，但我实在是不会拆，最后放弃了。

苦思冥想数十分钟后只会 O(n^2) 的暴力，最后得出结论——我不会做。

决定看题解。

题解区分为两大类，生成函数和几何意义

我们不会生成函数最后只能学习几何意义。

首先我们知道，从点 (0,0) 开始，每次只能向下或向右走，走到点 (n,m) 的方案数为 \binom{n+m}{n} ，那么我们对于一对 i,j ，就可以看做求从 (0,0) 走到 (a_i+b_i+a_j+b_j) 的方案数。然后如果我们要计算的话由于要枚举两个变量，时间复杂度是降不下来的。那么就考虑拆贡献，我们发现只要起点和终点构成的矩形的长宽不变，那么这个方案数就不变，所以它和起点以及终点的具体位置无关。

所以我们考虑平移这个矩形，将起点平移到 (-a_i,-b_i) ，那么终点就为 (a_j,b_j)。这样我们发现 i 和 j 就分开了，因为值域比较小，所以我们考虑DP。

随随便便打个 O(V^2) 的DP，即可。最后扫一遍统计答案即可。

但我们发现它会算重，重复在于 i<j ，我们将 i=j 和 i>j 的都算了一遍，对于前者，我们可以用组合数统计去重，对于后者，直接 \div 2 就行了。

AGC002D

依然是远古 AGC，题目质量依然很高！但我们这次没看题解就把它做出来了，哈哈哈哈。

先简单描述一下题意：

给你一颗 n 个节点 m 条边的无向连通图，有 q 次询问，每次询问告诉你两个不同的节点 x_i,y_i 和一个限制 z_i，将代价定义为从这两个点一起出发，走到至少 z_i 个节点，走过的编号最大的边的编号，可以重复走过一个点，但只算走到 1 个点，问你最小的代价是什么。

n\le10^5, m\le 10^5, q\le 10^5

额，题意还是一如既往的描述不清，算了，将就着看吧。

首先我们发现其实很多边都是没用的，因为我们可以重复走过一个点，所以真正有用的是这个图的最小生成树上的边，边的权值定义为边的编号即可。

可我们发现只维护最小生成树是没有用的，因为我们依然不知道该怎么最小化这个走过的编号最大的边的编号，然后我们想起了前几天用过的Kruskal 重构树，这个东西就是每次按边权从小到大加进来一条边时，不直接连上这条边，而是新建一个点，将儿子设为这条边连接的两个节点所在重构树的根节点，并将点权设为边权，这样很明显可以发现构成了一颗二叉树的形式。

这样有什么用呢？这个重构树有很多性质，一般都跟两个节点的 lca 有关，详情请见 OI-Wiki。

这道题我们发现，要最小化最大值，考虑二分。二分出来一个答案 mid 怎么快速判断可不可行呢？我们发现可以在重构树上找到点权小于等于 mid 的点 x_i,y_i 的祖先，然后再在建重构树的时候对于每个点记录子树内有多少个原图的点，这样直接将找到的祖先的值加起来就是此时最多能走到的点数，因为我们发现重构树一个以点 u 为根的子树内所有点的点权都小于点 u 的点权，所以该做法是对的。

而找祖先我们可以倍增找。

所以总时间复杂度为 O(n \log^2n)，已经够了。

第一次自己不看题解做出来了一道AGC的题耶。 \^_^

AGC002E

又是一道想半天不会做的题，但一看题解茅塞顿开。感觉我智力有点问题

先来讲一下题目大意：

有 n 罐糖，第 i 罐糖有 a_i 颗糖，两个人轮流进行以下两种操作中的一个：

吃掉最后一颗糖的人输，问谁有必胜策略（先手或后手）。

n\le 10^5,a_i\le 10^9

先一看，博弈论，再一看，可以排完序然后差分，这样两种操作就变成了可以把最前面的数 -1 或直接抹除最后面的一个数。

然后……，然后就卡死了，放弃思考，开始看题解。

题解区的想法十分巧妙，把题目转换为另一个题目来做。

还是要先排序（从大到小），这是我思路唯一和题解一样的地方。

具体来说，就是我们可以对题意做一个转换，在一个网格图上，我们刚开始在点 (0,0) ，其中第 i 罐糖我们转化为点 (i,a_i) ，然后我们按网格图依次连接。

比如对于序列：

7 5 3 3 1

它画出来长这样：

我们这样就把两种操作分别变为向右走一步或者向上走一步，两人轮流走，走到边界的人输。

我们发现红线上的点都是必胜点，因为走到红线前的上一步的那个人已经取走了最后一颗糖。

那对于红线围起来的点该怎么确定是必胜点还是必败点呢？

我们发现它可以这样转移：对于一个不在边界上的点 (x,y)，如果 (x,y+1) 和 (x+1,y) 中有一个是必胜点，那么这个点就是必败点，否则就是必胜点，正确性显然。

最后我们判断点 (0,0) 是不是必胜点就可以了。

打一下表我们不难发现，对于对角线上的点，它们的状态都是一样的。

所以我们可以找到最大的正方形的顶点 (i,i) ，看看它到上边和它右边的最远的非边界的点的距离，如果有一个是奇数，那么这个点就是必胜点，否则就是必败点。

然后就做完了，这种转化题意的套路第一次见耶！

AGC002F

AGC 继续冲冲冲，今天来做组合计数。

简述题意：

有 n 种不同颜色的球，每种颜色的球有 k 个，现在让你把它全部拿来排列，排列完后将每种颜色最左边的第一个球涂成白色（一种不属于原来颜色集的颜色），问你有多少种不同的排列，答案对 10^9+7 取模。

n,k\le 2000

我刚开始想的时候是一直在想直接计数，但后来看了数据范围才发现应该不能直接计数，不然怎么会开这么小。

后来转变思路，想 DP，但发现要么不会转移，要么状态数太多。好吧，投降看题解。

题解也是 DP 。我们发现构成一个合法的排列的充要条件是任意前缀的白球个数都大于等于颜色种类数（不包括白色）。我们想到可以设一个状态 f_{i,j}，表示我已经在 n 个位置中放了 i 个白球，并已经放完了 j 种颜色的球。很明显，j\le i 。

我们发现我们直接做的话会算重，所以我们钦定每次处理一种颜色或填一个白球时第一个球一定要填到第一个空位处，这样就不会算重。

好，来列转移方程：

f_{i,j}= \begin{cases} f_{i-1,j}\quad 当放一个白球时 \\ f_{i,j-1} \times[n-(j-1)] \times \binom{nk-i-(j-1)(k-1)-1}{k-2}\quad 当选择放一种颜色的球时 \end{cases}

稍微解释一下第二条转移式，先选一种颜色，然后把第一个空位填了，然后用组合数处理填后面的方案数。

特判 k=0 的情况。

一道练习组合计数的好题。

AGC073A

虽然是道A题，但是别笑，笑了你也和我一样只能花一个上午才能写出一个巨难写的做法。

简单描述题意：

给你一个周长为 L 的圆，随便指定圆周上一个点作为起始点，定义圆周上一个点的位置为从起始点出发，沿圆周顺时针走到这个点的弧长。接着有 n 个点，第 i 个点的位置为 a_i。这个圆上有 n 条弦，每条弦连接位置分别为 a_i 和 a_i+K 的两个点。我们可以从中选出任意数量的弦，然后我们把没选的弦擦掉。那么这个圆就被分割成了很多块。我们把包括圆心的那一块涂成白色，把和这个块相邻的块涂成黑色，最后把这个图的价值定义为黑色块的数量，问你所有选择方案的价值和。

2K<L\le 10^9,n\le2.5\times10^5

先写一下我们在赛场上的思考：

先随便画几个图，发现黑色块的数量和弦的位置关系有强相关性(废话)。然后我们注意到每次加入一条弦，黑色块增加的数量似乎和交点数量有关，但是好像还和开头块的颜色也相关，不好计数。我们放弃这条思路。我们接下来想到可以破环成链，我们发现，这个想法很有前途，因为操作被我们传化成了，在一个初始全是 0 的序列上，每次给一段区间异或 1，最后查询 1 的段数，但是依然有个很棘手的问题，序列长度过长，且开头和结尾也相邻，要去重。好吧，不会了，思考无果。

现在来写一下赛后改题思路：

我们发现，一个区域是黑是白取决于包围它的弦的数量的奇偶性。然后我们考虑对这个进行计数。

我们依然先破环成链一下，先暂且不论首尾相邻的问题。我们发现我们可以枚举一个区间 i，统计出如果一定要选 i 这个区间的贡献，然后把这个求和一下就可以了。

什么？你问我怎么算贡献？我们再统计出有多少个区间右端点在这个区间内，注意，如果一个区间的右端点刚好是第 i 个区间的左端点我们是不把它统计进去的。记作 s。本人刚开始发现答案是如下式子：

\sum_{i=0}^{s} \binom{s}{i} \left\lceil \frac{i}{2} \right\rceil

想直接算，发现不太行，所以换个思路。发现答案就是：

\sum_{2i\le s} \sum_{j=2i}^{s} \binom{s}{j}

为什么，因为发现上面的那个式子就是方案数乘上贡献，我们把贡献拆到每一步去算，这样就变成了下面那个式子。

我们再在草稿纸把这些组合数拼一拼，就可以发现是可以拼成一个好算的式子的，自己思考去。

然后就做完了。

CF

我们也是开始做了CF的杂题了，好吧！

CF518D

这道题其实是 qbf！ 讲的杂题的弱化版，但还是做了我很久。看看什么时候做了那道杂题好吧。

先简述题意：

给你 n 个三元组 (a_i,b_i,c_i)，求下列式子的值：

\sum_{i=1}^{p_1}\sum_{j=1}^{p_2}\sum_{k=1}^{p_3}\prod_{z=1}^{n}[[i>a_z]+[j>b_z]+[k>c_z]\ge 2] n,p_1,p_2,p_3\le 5\times 10^5

首先我们发现这不是一道简单的三维偏序板题，因为它让我们计数，并且是三维中只需要两维偏序即可。

我们想到可以先降维，将三维问题降成二维的问题来做。

先在草稿纸上列个二维的表格，第 x 行第 y 列上的数字就代表当上式的 i=x,j=y 时，可行的 k 有多少个。

例如该题的第一个样例在没考虑所有限制时的表格长这样：

5 5 5 5
5 5 5 5
5 5 5 5
5 5 5 5

我们现在将第二个三元组限制 (1,3,4) 考虑进去这个表格会变成什么样：

所以表格变成这样：

0 0 0 1
1 1 1 5
1 1 1 5
1 1 1 5

把上述过程推广一下，我们就得到了 n^2 的做法。

但我们发现一个一个点看太浪费了，考虑一行一行统计看来加速计算。

我们设 x_i 表示第 i 行第二个操作的值，y_i 表示第 i 列第二个操作的值，z_i 表示第 i 行有多少个被赋值成零的数。

我们发现第二个操作就是在让一段 x 与一个数取 min，相当与前缀 min，y 也同理。

这样的话 x,y 就都是单调不上升的了，

先不考虑被赋值成 0 的点，我们看看怎么计算答案。

对于第 i 行，我们可以找到一个位置 t ，使得纵坐标 j\le t 的点的值取 y_j ，纵坐标 > t 的点取 x_i 。

前一个可以用前缀和，后一个直接算。

求 t 可以用一个指针，因为单调性。

然后在考虑被赋值成 0 的位置就行了，时间复杂度 O(n)。

一道不错的小清新题。

CF2127H

一道 VP 比赛里的最后一题，当时因为 D 题导致心态调崩，没心情也没时间打这道题了。

正解还不会，但我们会偏解。

简单概括题意：

给你一个 n 个点 m 条边的无向图，保证无重边自环，且每个点最多在 5 个简单环中。定义一个原图的子图是合法的当且仅当子图中每个点的度数不超过 2。问合法子图边数最大是多少。

n\le 30 ,m\le \frac{n(n-1)}{2}

我们首先想到一个非常直接的贪心，就是依次加入每一条边，看看加入这条边后是否合法，合法就加入，否则就不加入。

但很显然，它是错的，不然 n 就不会这么小了。

不难发现当出现一个 n 个点的简单环，并且在中间多了一条边时。我们的程序就很可能算错。

通过思考，注意到边的顺序是关乎答案大小的，再加上 m 很小。脑子里就得想到随机化乱搞。

具体而言就是用模拟退火，每次随机交换两条边的顺序再跑贪心。

然后就过了，还挺快。

洛谷

没错，还有洛谷。

[KTSC 2022 R1]直方图

还没做出来！！！

[JSOI2018] 战争

在打上面那道题时发现闵可夫斯基和有点不太会，于是决定复习一下，便找到了这道题来练练手。

简单描述题意：

给你一个由 n 个点围成的凸多边形 A，和一个由 m 个点围成的凸多边形 B。q 次询问，每次问你将凸多边形 B 沿一个方向平移一定长度后，与凸多边形 A 是否有交集。

n\le 10^5,q\le 10^5

首先得先否定自己脑袋里那个将图形 B 平移然后快速判断的想法。

我们考虑对于一个询问 (a,b) 怎么样会有交集。

就是满足如下条件：

\exist (x,y)\in B \ 且\ (x+a,y+b)\in A

写得不那么严谨一点就是：

B+\vec{x}\in A\\ \vec{x} \in A-B

这和属于号右边和询问无关啦！

所以我们可以用闵可夫斯基和维护出这个所谓的 A-B ，然后快速判断向量 \vec{x} 是否在这个凸包内。

所谓的 A-B 其实就是把 B 中的点全部取反，然后就变成了 A+(-B) ，这就是很经典的闵可夫斯基和了。

但我并不会直接维护凸包，且我也不知道怎么判断一个向量是否在一个凸包内，于是我用了一点人类智慧。

分别维护上凸包和下凸包，然后 A 的上凸包和 B 的上凸包合并，A 的下凸包和 B 的下凸包合并。这样就是判断一个纵坐标是否在一个区间内，这个离线下来的话很好做。

最后来细说一下闵可夫斯基和，就以合并上凸包为例。

可以证明两个上凸包合并后形成的上凸包边数为原本两个凸包的边数之和，换句话说就是新的凸包的每条边都是原本两个凸包的边，所以我们可以类似归并排序，把两个凸包的边按斜率排序，再算一下左下角那个点坐标，这样一整个凸包就确定了，线性时间复杂度，十分优秀！

数列分块系列

洛谷也有，题目名称相同，自己搜，难度不高。

在这个系列里，你将见识到分块文化的博大精神，什么数据结构的板题都能做。进可考场切黑题，退可无脑骗高分，真可谓是灵活通用的算法，算是必学数据结构之一。

数列分块入门 1

水题，线段树秒了

为了 尊重作者 锻炼分块的能力，我们还是来打一下分块吧。

简单描述题面：

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。

n\le 3\times 10^5

真的没什么好讲的，把数列分成 \sqrt{n} 的块，每个块维护一下加法标记，对于散块单独处理查询和修改，这样就可以做到 O(n\sqrt{n}) 的时间复杂度。

数列分块入门 2

本人认为这是分块入门的第一道坎。

简单描述题意：

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的元素个数。

n\le2\times 10^5，-2^{31}\le x\le 2^{31}-1

这个的难度略大于上一题，首先查询元素个数，我们自然而然想到的就是桶，然后小于等于 x，就是维护一下前缀和。

但是 x 很大，桶开不下，怎么办呢？

聪明的你一定想到了，可以离散化+二分，详细来说就是把块内的元素排序，然后每次查询就是散块暴力查，整块二分查就行了。

那修改怎么办呢？一样的，我们发现如果修改的范围包括了一整个块，那么块内元素相对大小不会改变，所以就直接维护一个加法标记即可，散块也是直接暴力修改，然后暴力排序即可。

时间复杂度大概是 O(n\sqrt{n}\log n)。应该过得了。

数列分块入门 3

简单描述题意：

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内某个值 x 的前驱。

n\le2\times 10^5，-2^{31}\le x\le 2^{31}-1

其实和上面那道题一样，改几个 byte 就可以了，不多啰嗦。

数列分块入门 4

又是一道线段树板题。

简单描述题面：

在长度为 n 的数列上执行 n 次操作，操作包含区间加法，区间求和。

n\le 3\times 10^5

同数列分块入门 1，就不多啰嗦了。

数列分块入门 5

暴力题。

简单描述题意：

给出一个长为 n 的数列 a_1…a_n，以及 n 个操作，操作涉及区间开方（下取整），区间求和。

n\le 3\times 10^5,0\le a_i\le 2^{31}-1

注意到一个数顶多开 15 次平方就会变成 1 ，而变成 1 后就不会再变小了，所以我们依然分块。对于每个块我们维护不是 1 的数的数量，如果不为 0 就暴力修改，否则不修改，求和也是一个套路。记得考虑 0。

数列分块入门 6

一道块状链表的板题。

简单描述题意：

给出一个长为 n 的数列，以及 n 个操作，操作涉及单点插入，单点询问。数据随机生成。

n\le 3\times 10^5

要支持快速插入。很明显，不是平衡树就是链表，在这里笔者打的是块状链表。

块状链表就是在链表上分块，我们知道链表是不支持随机访问的，一个个跳时间复杂度将会达到惊人的 O(n)。

所以我们考虑分块，将 \sqrt{n} 个元素单独拉出来拼成链表，每条链表的表头再用链表存一下。

这样查询就可以做到 O(\sqrt{n})。

那插入呢？我们发现有可能经过不断插入，一条链表的长度可能很长，所以为了保证暴力的时间复杂度是对的，当一个链表很长时，我们就要从中间断开，分成一个新链表，这样插入时间复杂度也可以做到 O(\sqrt{n}) 了。

记得维护一下元素在该块链表里的编号，方便分裂。

数列分块入门 7

不是，怎么这么喜欢用分块做线段树的板题啊！！！

简单描述题面：

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间乘法，区间加法，单点询问。

n\le 3\times10^5

真的不想多说什么，对于每个块维护一个加法标记，一个乘法标记即可。

数列分块入门 8

珂朵莉树的题，分块也能做！！！

简单描述题面：

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间询问等于一个数 c 的元素，并将这个区间的所有元素改为 c。

n\le3\times10^5

我们注意到每对一个整块进行一次操作，这整个块就会被推平，全部变成一个数。所以随着操作数量不断增多，原数列的数的种类一定会越来越少。所以对于散块，我们暴力查询，对于没有被推平的整块，我们也暴力查询，而被推平的整块，我们直接算就行了。

数列分块入门 9

这几道题里面最难的题，你要是能独立思考出来，你就可以算是分块入门了。

简单描述题面：

给出一个长为 n 的数列 a，以及 n 个操作，每个操作即询问区间的最小众数。

n\le 3\times10^5

很好，我们乍一看似乎没有思路，因为查询区间众数并没有一个好办法。我们最暴力的想法很明显是离散化后看看哪个数最多，但这个似乎不能加上分块优化，那该怎么办呢？

我们想不到做法，但看题目名称我们知道肯定是分块。所以我们可以先把数列的块给分了。把原数列分成一个个块。那我们有个很显然的想法就是我们维护出块中的的众数，然后我们猜测答案肯定是这些数中的一个，然后我们一个一个用 O(n) 的时间复杂度检查就行了。

但很遗憾，这样并不对。因为区间众数这个信息并不能合并，就比如每个块的众数个数为 k 个，且这些众数两两不同，但是还有一个数在每个块中的个数都为 k-1。那你这个方法就查不到了。但这给了我们一个启发：我们既然对于每个块维护信息再合并不行，那我们就对每多个块都维护出一个信息！

具体来说，就是我们求出一个 p_{i,j} 和 num_{i,j} 分别表示从第 i 个块到第 j 个块的区间众数及其个数。这个我们可以在 O(n\sqrt n) 的时间复杂度内求出。

但是我们还有散块呢！这个好办，我们直接暴力枚举散块里的数，然后求出它在这个区间里的个数，看看是否能成为答案即可。

但这次我们不能再暴力遍历整个区间了，我们得优化一下。简单来说就是求出一个 s_{i,j} 表示从第 i 个数开始，到第 j 个块末这段区间中 a_i 出现了多少次，这样中间的遍历就被省掉了。后面的散块也一样。

这样我们就完成了这道题，时间复杂度 O(n\sqrt{n})。

考虑双倍经验 [Violet] 蒲公英。

[CEOI 2021]Newspapers

2021CHD 讲的杂题，一道十分有趣的构造博弈论题。

我们先来简述一下题意：

有一张 n 个点 m 条边的简单无向连通图，有两个玩家 A、B，玩家 B 一开始在某个节点，但是玩家 A 并不知道它在哪里，然后两个玩家轮流执行以下操作：

求玩家 A 是否有一个策略使得无论玩家 B 在哪个节点，玩家 A 最后都能获胜，如果有的话请构造一个策略，使得最坏情况下玩家 A 猜测的次数尽量的少。

n\le 1000,m\le \frac{n(n-1)}{2}

毕竟是道黑题，我们放个提示吧！Hint\ 1：先考虑有解的充要条件。

什么，你居然想到了？那我们再给你个提示。Hint \ 2：考虑链怎么做。

那我们现在来讲一下正解。首先我们考虑一下有解的充要条件，我们发现如果出现了一个环的话，一定无解，因为这个游戏本质上就是通过一次次猜测排除玩家 B 能在的位置，但如果有一个环的话，玩家 B 就可以躲在环里不出来，这样我们无法排除它所在的位置。所以当 n\le m 的时候无解。

但其实并不是只要图为一颗树就有解，如右图：

我们这里给出树有解的充要条件：如果存在一个点存在三个深度大于 2 的子树的话就无解。

具体证明就是假设我们已经排除了上图的一个子树，我们接下来应该怎么办。我们手玩一下就会发现我们无论如何都要么会使得玩家 B 有可能走回已经排除的子树，要么就无法排除完任何一颗子树。

好的，现在剩下的情况就只剩下有解的了，要求我们构造一组最下猜测次数的策略，我们先考虑链怎么做。思考 30 分钟后相信大家都想到可以从链的一端的第二个开始猜，猜到链的另一端的倒数第二个，然后反着再来猜一遍，这样就一定可以把玩家 B 猜出来。具体怎么证明这个最小我也不知道，先咕着……

接下来我们考虑正常的树怎么做，既然上面那个方案是最小的，那么我们很自然的可以想到可以把直径拿出来跑这个，但是可能还挂了些别的，怎么办呢？大佬 2021CHD 给出解决方案：

然后就完结撒花啦！

[CTS2025] 士兵

随机跳题跳的题，发现居然是 CTS/WC2025 的题，让我们来看看难度如何。

奋战近 2h 后无果，求助场切这道题的 lnw143 大巨。

先简述一下题意：

有从左到右依次排开的 n 个位置，第 i 个位置站着一位血量为 a_i，贡献为 b_i 的士兵。每次我们可以选定一段区间 [l,r]，并花费 m 的代价使得这段区间里的士兵血量减少 1 。当一个士兵的血量 \le 0 时，它就会带来 b_i 的贡献。求最大的贡献与代价的差。

n\le 5\times 10^5 ，1\le a_i\le 10^9，\textcolor{red}{-10^9}\le b_i\le 10^9

注意！！！贡献可以是负的。

首先拿到这道题的第一个想法是贪心，本来想的是反悔贪心，但是不会贪。所以换个思路，想 dp。但依然无果。

关键是这道题还没题解！---------2025.10.15

还好我们有场切的大巨在此，可以让我们求助。

首先正解确实是 dp。

先来考虑假如说我们知道每个位置打多少伤害该怎么最小化打伤害的贡献。

我们设 c_i 表示第 i 个位置打的伤害量。我们发现如果 c_i>c_{i-1}，那么就会产生额外的 m\times (c_i-c_{i-1}) 的代价。

所以我们设 f_{i,j} 表示考虑到第 i 个位置，当前位置打的伤害量为 j 的最大贡献。

枚举上一个位置的伤害量 k，所以有转移式：

f_{i,j}=\max_{k=0}^{maxa} \{f_{i-1,k}-\max(0,m\times(j-k))\}+[j\ge a_i]\times b_i

时间复杂度 O(nm^2)，根本过不去 T_T。

其实这个式子很有前途。

我们发现第一维其实没什么实际作用，所以滚掉。

我们又发现我们任意时刻其实都可以将任意一个数改成后缀 max，因为这样其实会使原来的情况更劣从而不影响答案。所以如果我们每做一轮转移后都求一遍后缀 max，操作，f 数组一定每一轮都是单调不递增的。

我们不考虑转移式的前面一部分，我们只考虑后面的额外贡献。这一部分其实相当于给一段后缀加上一个数。所以我们按 b 的正负性来分类讨论：

综上所述，我们又又又发现，这些操作都可以用线段树快速维护。

最后时间复杂度离散化后是 O(n\log n) 的。

如果你要离散化那你要注意，真正有效的位置不止那 n 个，还有每个 a_i-1。

[集训队互测 2011] Crash 的文明世界

这道题是在刚讲Stirling数时去做的，还不错，不是很难，奋战一会就搞出来了。

先来简述题意：

给定一颗 n 个点的树和一个正整数 k，对于每个点 i 求出下面式子在模 10007 意义下的值。

\sum_{j=1}^n dis(i,j)^k

其中 dis(i,j) 表示两点之间简单路径上边的数量。

n\le5\times10^4，1\le k \le 150

首先我们先来简单介绍一下第二类斯特林数的定义。

定义：{n\brace m} 表示 n 个两两不同的小球，划分为 m 个两两不同的集合的方案数。

根据组合意义，我们有如下递推式：

{n\brace m}=m\times{n-1\brace m}+{n-1\brace m-1}

还是简单说明一下吧，前面一项表示对于新的一个球，我们放进前面某个集合的方案数，后面一项表示新开一个集合的方案数。

边界条件是 {n\brace 0}=[n=0]。

还有通项公式：

{n\brace m}=\sum_{i=0}^{m} \frac{(-1)^{m-i}i^n}{i!(m-i)!}

证明先咕着，本道题还用不到。

这些其实不是重点，重点是自然数幂与第二类斯特林数的关系。

我们有如下等式：

n^k=\sum_{i=0}^k i!\binom{n}{i}{k\brace i}

我们可以用组合意义证明一下。

而右式的组合意义为：把 $k$ 个球划分成 $i$ 个集合，然后从 $n$ 种颜色中选出 $i$ 种，给每个集合的球都染上互不相同的颜色，并保证每个集合的所有球染成相同颜色。因为是有序的，所以再乘上 $i!$。 这个有什么用呢？ 我们把贡献式化一下： $$ \sum_{j=1}^{n} dis(i,j)^k\\=\sum_{j=1}^{n} \sum_{s=0}^{k} s!\binom{dis(i,j)}{s} {k\brace s}\\ =\sum_{s=0}^{k}\sum_{j=1}^{n} s!\binom{dis(i,j)}{s} {k\brace s}\\ =\sum_{s=0}^{k} s!{k\brace s} \sum_{j=1}^{n}\binom{dis(i,j)}{s} $$ 现在会了吧？前面的一部分对于所有的 $i$ 都是相同的。所以我们只需要维护后面一部分即可。 我们有 $\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$。所以后面一部分的贡献我们换根就很容易维护了。