526互联

DP 总结

发布时间 2023-10-03 23:00:12作者: recllect_i

最小包含串

模型描述

给定两个长度分别为 \(n,m\) 字符串 \(s,t\)，求出长度最小的串，使两个串都是这个串的子序列。

基本解法

设 \(f_{i,j}\) 表示第一个字符串前 \(i\) 个和第二个字符串前 \(j\) 个字符的最短包含串长度。

边界：\(f_{i,0}=f_{0,i}=i\)。

转移：

\[f_{i,j} = \begin{cases} f_{i-1,j-1}+1 & (s_i=t_j )\\ \min \{ f_{i-1,j},f_{i,j-1} \} & (s_i \ne t_j) \end{cases}\]

时间复杂度 \(O(nm)\)。

扩展

最小字典序方案

首先提出最小字典序方案的套路：倒序递推，记录转移过程或者在完成递推后一个位置一个位置地判断。

最小包含串的每个字符在状态转移过程都是确定的，所以可以用任意一种方法求。

方案数

对于第一种转移，方案是在原方案上加上一个字符，所以方案数相同；对于第二种转移，由于最后一个字符不一样，可以直接相加，不考虑去重。

小结

最小包含串问题是线性 DP 中比较基础、扩展叫小的一类问题，思想较为简单。

最长公共子序列

模型描述

如题

基本方法

设 \(f_{i,j}\) 表示 \(s\) 前 \(i\) 个字符和 \(t\) 前 \(j\) 个字符最长公共子序列长度。

边界：\(f{0,i}=f{i,0}=0\)

转移：

\[f_{i,j} = \begin{cases} f_{i-1,j-1}+1 & (s_i=t_j )\\ \max \{ f_{i-1,j},f_{i,j-1} \} & (s_i \ne t_j) \end{cases}\]

时间复杂度 \(O(nm)\)

扩展

最小字典序方案

依然倒着递推，记录数组 \(nexts_{i,c},nextt_{i,c}\) 分别表示两个字符串中第 \(i\) 个位置即以后第一个 \(c\) 字符位置。

若在递推完成后判断，若当前在 \((i,j)\) 依次枚举子序列的第一个字符 \(c\) 如果刚好是最大值的转移，就直接到 \(nexts_{i,c},nextt_{j,c}\) 位置。

若记录路径，则对每个位置记录最长公共子序列的第一个字符最小是什么。

方案数

考虑去重。这里只需考虑第二种转移中两种方案都可以作为转移的情况，这时如果 \(f_{i-1,j},f_{i,j-1}\) 都可以由 \(f_{i-1,j-1}\) 转移过来，就需要减去 \(f_{i-1,j-1}\) 的方案。

对于 \(t\) 中元素互不相同的做法

转化为求 \(s\) 中每个元素对应的 \(t\) 中的位置的最长上升子序列。

小结

最长公共子序列扩展问题的难点在于可能不选择某些字符，这应格外考虑。

最长上升子序列

模型描述

如题

基本做法

1. 暴力 DP

设 \(f_i\) 表示以 \(i\) 结尾的最长上升子序列长度，则转移为：

\[f_i=\max\{f_j | j < i,a_j < a_i\}+1 \]

时间复杂度 \(O(n^2)\)。

2. 树状数组优化

首先对原数组离散化，令 \(g_i\) 表示结尾数字是 \(i\) 的最长上升子序列长度，则 \(f_i\) 可以用 \(g\) 的前缀最大值求，并用 \(f_i\) 更新 \(g_{a_i}\) 可以用树状数组维护。

3. 贪心+二分

设 \(g_i\) 表示长度为 \(i\) 的上升子序列结尾最小值，二分查找并进行更新即可。

注意，若使用这种方法，严格用 lower_bound 不严格用 upper_bound！

扩展

转化 DAG 问题

\(s -> 1\dots n\), \(1\dots n -> t\), \(i -> j \left( i < j , a_i < a_j\right)\)

求最长路。

带权最长上升子序列

只需把转移中加一换成加权值。

仍可用树状数组优化。

最小字典序方案

倒叙递推，并在树状数组中记录最小的开头。

位置不同的方案数/本质不同的方案数

树状数组中记录取最大值时的方案数。这两种情况的区别是：位置不同的计算方案时加上新的方案数，本质不同的是覆盖之前的方案数。

判断数是否在最长上升子序列上/所有方案中

分别求以每个数开头和结尾的最长上升子序列长度，相加减一即包含这个数的最长上升子序列长度，与最大值比较就可以解决第一问。

对于第二问有两种方法：

  1. 比较经过这个数的方案数与不经过这个数的方案数是否相同。一般模一个（或者多个，双哈希）大（质）数（最好不是 \(10^9+7\) 之类的）比较，自然溢出容易出错。（实际上，这种方法对一般 DAG 是通用的。）
  2. 考虑不在所有最长上升子序列方案中的情况：左侧有最长上升子序列，右侧有最长上升子序列，左边右边拼在一起有最长上升子序列。对于最后一种情况，开 \(n\) 个 vector 存开头、结尾的上升子序列的长度是 \(i\) 的位置，可以发现开头的数依次递减，结尾的数依次递增，于是对于每种左右分配，用双指针扫一遍这种情况导致不是所有方案的区间。

二分的 g 数组变化

1. 整体左移、右移

记录移动的偏移量。

2. 整体加减

记录加减的值 \(t\)，后面的数当做 \(a_i-t\)。

应用：单 0 模糊（每个零可以替换成任意值）最长上升子序列

对于一个 0，它对 \(g\) 数组的变化就是整体加一右移。

开 vector 存二分的 g 数组修改历史

性质：

  1. 每个 vector 内部是单调下降的。
  2. vector 之间的 back（其实是 g 数组）是单调上升的。

运用这些性质，可以求：

  1. 最长上升最序列的值的最大字典序：倒序，找到以 a 开头的最长上升子序列长度后再找到能接的最大的下一个数；
  2. （位置不同的）方案：合法的转移是 vector 中的一个后缀，方案数是后缀和（两个前缀和相减）。
  3. 本质不同的方案：类似于上一种，只是在加入元素时，如果是相同元素需要覆盖。
  4. 求那些数一定在最长上升子序列中的点。

随机排列的最长上升子序列期望长度

这个长度和 \(\sum f_i\) 的期望值都不会很大（长度的期望是 \(O(\sqrt n)\)，约为 \(2\sqrt n\)），可以用这个性质乱搞一些数据随机生成的题。

最长上升子序列与路径经过最多点数问题

问题描述：初始位于 \((0,0)\)，当在 \((x,y)\) 时可以走到 \((x+1,y)\) 或 \((x,y+1)\)，有一些不重复的点，求一条路径走过的点数量的最大值。

解决方法：把所有点按横坐标由小到大排序求纵坐标最长上升子序列。

最长上升子序列与最小下降子序列包含

问题描述：用至少多少个非严格下降子序列才能包含序列中所有数。

解决方法：答案是最长上升子序列。

最长上升子序列与线段树合并

问题描述：给定两序列 \(a,b\) 求 \(b\) 接到 \(a\) 后的最长上升子序列。

解决方法：对两个序列建立线段树，其中表示区间 \([l,r]\) 的节点记录 \(f,g\) 表示开头、结尾在 \([l,r]\) 中的最长上升子序列，然后合并两棵线段树，合并过程中，对于都存在的一个节点 \([l,r]\) ，则 \(a\) 中 \([l,mid]\) 结尾 \(b\) 中 \([mid+1,r]\) 开头的所有上升子序列可以合成一个上升子序列，于是可以把第一棵线段树节点的左儿子的 \(g\) 加第二棵线段树节点的右儿子的 \(f\) 的值计入答案。

全0模糊（将所有0统一替换为某个值）最长上升子序列

非严格

所有的0模糊后的结果在最长上升子序列中只会在一段出现，可以用线段树维护结尾的数是a的中间没有模糊的零（最后可以有）的最长上升子序列长度和中间有模糊的零的最长上升子序列长度。 扫一遍数组，如果是零把所有中间没有零的最长上升子序列长度加一，不是零可以有三种转移：没到没，没到有，有到有。

严格

与非严格类似，最多只有一个零在最长上升子序列中。要维护中间有零（但没有加入）和中间没零的情况和已经用了零的情况。扫一遍数组，如果这个数是零，把所有中间没有零的转移到中间有零的（每个数只需要转移一次），不是零的情况类似。

二维最长上升子序列

实在不行 \(O(n^2)\) 暴力吧。

可以用一种 CDQ 分治的方法。CDQ 分治优化 DP 有三个过程：分治左半部分；用左半部分结果更新右半部分；分治右半部分。这样可以保证每个状态都被满足要求的状态转移到且在更新其它状态之前完成更新。二维上升子序列满足三维偏序，套用处理三维偏序的方法做第一维，而用刚才的树状数组方法做第二维，时间复杂度 \(O(n\log^2 n)\)。

动态插入的上升子序列（离线）

用树状数组二分求出所有数最终位置，并按插入顺序加入时间这一维，转化为二维最长上升子序列。

小结

最长上升子序列是一个运用比较广泛的问题，常结合树状数组等数据结构考。

背包问题

基础

01 背包、完全背包、多重背包、分组背包、负数体积的背包、天平背包、多重限制的背包、计数背包。

树上背包、状压背包、概率背包。

方案数、最小字典序方案。

体积与价值转换

有时候可以把价值当作体积跑背包，获得更好的复杂度。

01 背包与 bitset

  • 方案存在性：f |= f << v

  • 方案数模 2： f ^= f << v

  • 带取模的背包： f |= f << v | f >> M - v

  • 对体积贡献是乘法对质数取模的背包：用原根把乘法转换为加法。见2017。

多重背包单调队列优化

枚举除以体积的余数，再枚举商。

对于每个余数，方程 \(f_i=\max_{j=0}^{j\leq c}\{g_j-wj+wi\}\) 可以用单调队列优化。

计数背包的排列计数

记录物品个数，统计时乘阶乘，或者直接把阶乘计算带入转移方程。见计数。

计数背包的拿出问题

观察转移方程 \(f_i=f_i+f_{i-v}\)，可以还原回去 \(g_i=f_i-g_{i-v}\)。

跟质因数有关的状压 DP

见 寿司晚宴 和 无平方数

关于概率问题

由于能力有限，解决这类问题的主要方法是计算方案。

但有的题会除到比较小的数，或之前成到较大的数，导致精度误差大，可以考虑把最后的计算带入到 DP 的转移方程（见 21点）。有时候带入方程可能得到更低的复杂度（见 随机函数）。

各种形而上学？

大多重背包，小体积

问题描述：（大背包）一个体积为 \(m\) 的背包和 \(n\) 种物品，每种物品有体积 \(v\) 和使用次数上限 \(c\)，求能装进背包的最大体积，\(m\leq10^{18}\)，\(c\leq10^{16}\)。

解决方法：如果装不满，就直接输出。先贪心地装，但每个物品都要留点数量，背包也要留一些体积，然后多重背包。

理解/证明：我太菜了，不会证明，感性理解一下把。@Fiyuls 大佬证明了预留物品数和体积大于 \(lca\{1,2,\dots,n\}\) 时基本正确。

带负数体积背包的科学优化

问题描述：（拔河比赛）求带负数体积背包体积等于零的最大价值，\(n\leq 1000, v\leq 1000\)。

解决方法：打乱，然后数组开小一点跑背包。

理解/证明：部分证明如下：

即证明对于任意一个和为 0 的序列，随机排列后前缀和的最大绝对值大于序列绝对值最大值的若干倍概率很低。

考虑一种简单情况（CF1240E 的简单情况）：一个由 \(n\) 个 1 和 \(n\) 个 -1 组成的序列，前缀和大于等于 \(k\) 的概率。

与卡特兰数相似，考虑网格图，一开始在 \((0,0)\) 位置，把每个 1 当作向上走，把每个 -1 当作向右走，最终会走到 \((n,n)\) 位置，1 和 -1 分别进行排列，则总方案数为 \(C_{2n}^nn!n!\)。

每种前缀和大于等于 \(k\) 的方案必然经过直线 \(y=x+1\)，在经过这条直线的第一个位置的后面部分对直线 \(y=x+1\) 翻转，最后可以到 \((n-k,n+k)\)，则总方案数为 \(C_{2n}^{n-k}n!n!\)。

则概率

\[P=\frac{C_{2n}^{n-k}n!n!}{C_{2n}^nn!n!}=\frac{n!\cdot n!}{(n-k)!\cdot (n+k)!}=\frac{\prod_{i=n-k+1}^ni}{\prod_{i=n+1}^{n+k}i} \]

当 \(n=1000,k=50\) 时，这个数值约为 \(0.0821021100\)。

当 \(n=1000,k=100\) 时，这个数值约为 \(0.0000448714\)。

体积和价值都大的 01 背包

问题描述：（背包问题）\(n\) 个物品体积为 \(m\) 的 01 背包，物品信息随机生成，\(n\leq 100, v\leq 10^9\)。

主要有三种方向：深搜剪枝，宽搜剪枝，随机贪心。

深搜剪枝

  • 令 \(r=5\times 10^4\) 表示缩小比例，对每个后缀物品组，背包容量上限设为 \(\lceil \frac{m}{r}\rceil\)，物体体积设为 \(\lfloor \frac{v_i}{r}\rfloor\)，则对于 \(i\) 个物品之后所有物品体积为 \(m_0'=\lceil \frac{m_0}{r}\rceil\) 的背包，得到的结果一定大于真实结果且比较接近，于是就可以借助这个结果进行剪枝。原题 TLE70。

  • 效率低下的原因是体积比较小的时候基本不能剪枝，所以无耻的我体积比较小的时候可以直接跑背包。原题 AC。

宽搜剪枝

参考 @Fiyuls 大佬文章和 @Xseventh 的解法。

  • 宽搜的时候一些不太优秀的状态直接不管。

  • 具体实现不需要太复杂，由于数据随机性，只需要把体积较大而价值小的方案放弃。同时把物品体积从小到大排序，当一个状态装不下当前物品，说明以后的物品也装不下了，这时可以计算答案并放弃。原题 AC。

随机贪心

参考 @Fiyuls 大佬文章。

  • 按性价比排序，随机几次选择性价比较大的物品选择的概率更大。

  • 为了避免没有多少不选第一个物品的情况，可以从后面某些地方跑几次保证有一些没选到前几个物品的情况。原题 WA90。

背包与分治（留着备用）

题目

题解

背包与决策单调性分治（留着备用）

题目

题解

区间 DP。

\(\color{white}\text{好可爱啊好可爱啊好可爱啊好可爱啊好可爱啊好可爱啊好可爱啊好可爱啊}\)

常见方法

  1. 找划分点。
  2. 取两端、一端。

常见模型

枚举分段

找出区间中一个地方为中间节点，比如枚举二叉树中序遍历的根节点。

找出一个点，左边、右边分别在不同的区间中，比如石子合并。

如果要求计数，第一种情况天然地去了重，但第二种可能有多个断点导致在每个断点都会统计答案，这里可以强制左边一段有特殊性质使它不能再进行划分（见括号序列）。

多边形剖分问题，对于凸多边形，\(f_{l,r}\) 表示点 l 到点 r 之间边和 l 到 r 的对角线组成凸多边形状态，转移枚举与 点 l、点 r 组成三角形的点 k，划分为两个凸多边形和一个三角形。答案是 \(f_{1,n}\)，不需要破环成链。如果是凹多边形，需要借助一些计算几何的方法判断对角线是否在多边形内部。

一般没有特殊性质的环形问题可以考虑破环成链。

取端点与涂色

取端点一般用于括号序列和从两端取的问题。有时候可以结合费用提前计算（见关路灯等题目）。

涂色问题见题目。

连续颜色段消除

问题描述：可以选择一段颜色相同的段，把它消除并计算贡献，贡献与颜色段的长度有关且随颜色段长度增加，求消除完后最大贡献。（祖玛游戏、方块消除）

设 \(f_{l,r,k}\) 表示区间 \([l,r]\) 后面有 \(k\) 个连续的颜色 \(c_r\) 的最大贡献。首先将与 \(r\) 相邻且同色的拿出来，直接计算贡献，或者消除中间的一段后接到某个段的后面凑成更长的段。答案为 \(f_{1,n,0}\)。用记忆化搜索实现比较简单。

更多的模型

\(\color{white}\text{好可爱啊好可爱啊好可爱啊好可爱啊好可爱啊好可爱啊好可爱啊好可爱啊}\)

与区间最小瓶颈有关的，按瓶颈划分区间，或建笛卡尔树。

树上 DP

换根 DP

求出每个点为根的答案。套路：

  1. 第一次 dfs，求出有根树子树的答案
  2. 第二次 dfs，加上父节点子树的的贡献。首先求父节点删去这个子节点的答案，然后用这个答案贡献这个子节点数组。删去：+/-：直接加减；max/min：存最大、最小值；mod：存子节点信息前缀、后缀。

运用的重点在于看出是个换根 DP。

顺便说一下，有一些路径相关的树上问题可以通过合并当前子树和未计算的子树统计答案。

几道题：POJ3585，HDU5834。

重心

使子树的 size 最大值最小的点。

性质：

  • 重心最多有 2 个，且其中一个是另一个父亲；
  • 重心的子树大小不超过 \(\frac{n}{2}\)；
  • 增加或删除一个叶子节点，重心最多移动一条边。
  • 重心一定在根节点所在的重链上。
  • 重心一定是重儿子所在子树重心的祖先。利用这条性质可以 \(O(n)\) 求每棵子树的重心。

直径

最长链。

求法：两次 dfs；DP 路径合并（不用换根）。

直径合并：两棵树用一条边连起来，组成一棵新的树，新树的直径的端点一定在原树直径端点。

概率与期望

没错，要考。当然选拔考试的难度肯定是要比 pkusc 的要低的。

狼人杀

你在一局狼人杀游戏中扮演狼人角色，不幸的是，只有你一个狼人，但是预言家也只有一个。在这局游戏中，预言家可以验一个区间就能知道这个区间有没有狼人。已知游戏人数你的位置，预言家乱验（即随机一个合法区间验人）的情况下你的身份被预言家准确知道的期望轮数。\(n\le150\)，但 \(n\leq50\) 有 50 分。

我太菜了，不会，望大佬解答。

@Fiyuls 的 50 分做法，感谢。

一般套路

一般期望的 DP 顺序是从后往前，概率从前往后，但也有其它情况。

先看结果在决策和决策完再看结果的区别

见换教室。

如果要先看结果再决策，可能要 \(f_{i,1/2/3}\) 表示前 \(i\) 个课程第 \(i\) 个不换、申请未通过、申请通过的最小期望。

转移成环

  • 自我转移的期望：初中方法可以列方程求解。

  • 一种成环的转移：\(f_0\) 能转移到 \(f_{1,2\dots n}\)，而 \(f_i\) 能转移到 \(f_{i-1}\)。可以把 \(f_i\) 表示为 \(f_0\) 的线性关系式。（未实践过）

  • 带决策：见弓箭强化。设 \(f_i\) 表示从 \(0\) 级到 \(i\) 即的期望步数，则满足

\[f_i=\frac{1}{AB}\sum_{a=0}^{A-1}\sum_{b=0}^{B-1}\min\Big\{f_i,\frac{a}{A}f_{i-1}+\left(1-\frac{a}{A}\right)\frac{b}{B}(f_{i-1}+f_i)+\left(1-\frac{a}{A}\right)\left(1-\frac{b}{B}\right)f_i\Big\}+1 \]

不能直接求，但可以发现所有选第一种转移的书满足一个不等式 \(f_i>g(a,b)f_{i-1}\)，其中 \(g(a,b)\) 是一个关于 \(a,b\) 的函数（自己算），于是对每本书按 \(g\) 排个序，然后算个数，甚至不用比较个大小，就能求个最小值。

动态树上概率 DP

请在“动态”后断句。

有一棵有 \(n\) 个节点的有根树，第 \(u\) 节点的 \(a_u\) 有 \(p_u\) 的概率为 \(1\)，有 \(1-p_u\) 的概率为 \(0\)，\(b_u\) 等于 \(a_u\) 和所有子节点的 \(b\) 值的众数，动态修改 \(p_u\) 的值，求根节点的 \(b\) 值为 \(1\) 的概率。\(n\le10^5\)。

我太菜了，不会，望大佬解答。

状压 DP

普通的集合类的如信息传递，这题的难点在于预处理贡献和卡空间。

区间极小值看起来是一个基于连通性的状压 DP，但如果安排从小到大的填数顺序是可以做到比较容易的转移的。同时这道题也启示当发现计数时存在问题，除了优化状态表示，也可以用容斥去掉不合法的方案。

当然，一般情况下状压是用来骗部分分的，但有时候也能启发想到正解。

线段树优化 DP

见怪物杀手，此题转换成求一些区间覆盖所有点的方案数。区间覆盖有关的问题可以按右端点排序计算贡献。

仙人掌 DP

每条边之多在一个简单环的图，充分条件是没有偶数环。

一般先思考树，再思考基环树，然后再思考仙人掌。

仙人掌转化为圆方树可以转化成树上问题，常见方法是圆点和方点分类讨论。

见旅行计划。

插入式的 DP

原本是一类排列的问题，但是可以规定一个顺序，比如从小到大插入到序列中，可以用连续段的方式实现，有时候要用到费用提前计算的思想。

见 CF704B、P9197。

一般套路：\(f_{i,j}\) 表示前 \(i\) 个数形成 \(j\) 个连续段，或者\(f_{i,j,0/1,0/1}\) 表示左右边界是否形成，转移有几种情况：新开一个连续段；作为一个插到已有连续段左边；插到已有连续段右边；链接两个连续段；作为左边界新开一个连续段；作为左边界接到个连续段左边；作为右边界新开一个连续段；作为右边界接到个连续段右边（在一些题目中，并不是要考虑所有情况，比如不区分左右的话可以把几种转移合并）。有两种理解方式，一种是连续段之间确定位置，另一种是连续段之间不确定位置。注意有边界情况的转移的细节。

李超线段树

思想与模板

用来解决这样的问题：动态加入函数 \(f_i(x)=k_ix+b(x\in [l_i,r_i])\) 表示一条线段，或 \(f_i(x)=k_ix+b(x\in R)\) 表示一条直线，给定 \(p\) 求 \(\min\{f_i(p)\}\) 或 \(\max\{f_i(p)\}\)，即直线 \(x=p\) 与当前线段或直线的交点纵坐标的最大值或最小值。

对于线段，如果这条线段不完全包含当前线段树节点对应的区间，则往左右儿子递归。

定义每个节点的优势线段为在这个节点的中点位置（可以不完全是 \(\frac{l+r}{2}\)，可以用左儿子包含区间最右边的位置）线段的交点纵坐标最大的线段。对于这个线段或直线包含这个节点的区间完全的情况：

  • 如果这个节点没有优势线段或新加线段完全覆盖当前优势线段，即左右端的函数值都大于当前优势线段函数值，设置这条线段为这个节点优势线段。
  • 如果条线段穿过当前优势线段，与它比较把在中点的函数值最大的设为优势直线，另一条设为需要加的直线。找到交点所在的儿子并用需要加的直线递归下去（可以通过计算函数值的方式确定交点在哪边，避免浮点误差）。

对于线段，时间复杂度 \(O(\log^2n)\)。对于直线，时间复杂度 \(O(\log n)\)。

查询则是从根节点到查询的叶节点优势线段的最大函数值，时间复杂度 \(O(\log n)\)。

LL F(int i, int x) {return k[i] * X[x] + b[i];}
void build(int u, int a, int b)
{
t[u].a = a, t[u].b = b;
if(a < b)
{
int mid = a + b >> 1;
build(u << 1, a, mid), build(u << 1 | 1, mid + 1, b);
}
}
void insert(int u, int p)
{
if(lx[p] <= t[u].a && t[u].b <= rx[p])
{
if(t[u].a == t[u].b)
{
if(!t[u].best || F(p, t[u].a) > F(t[u].best, t[u].a)) t[u].best = p;
return ;
}
LL ly = F(p, t[u].a), ry = F(p, t[u].b);
LL lz = F(t[u].best, t[u].a), rz = F(t[u].best, t[u].b);
if(!t[u].best || ly >= lz && ry >= rz) t[u].best = p;
else if(ly > lz || ry > rz)
{
int mid = t[u].a + t[u].b >> 1;
if(F(p, mid) > F(t[u].best, mid)) swap(p, t[u].best);
if(F(p, t[u].a) > F(t[u].best, t[u].a)) insert(u << 1, p);
else insert(u << 1 | 1, p);
}
}
else
{
int ls = u << 1, rs = ls | 1;
if(t[ls].b >= lx[p]) insert(ls, p);
if(t[rs].a <= rx[p]) insert(rs, p);
}
}
void insert(int p)
{
lx[p] = lower_bound(qt + 1, qt + q + 1, lx[p]) - qt;
lx[p] = max(lx[p], 1LL);
rx[p] = upper_bound(qt + 1, qt + q + 1, rx[p]) - qt - 1;
if(lx[p] <= rx[p]) insert(1, p);
}
LL query(int u, int x)
{
LL ans = t[u].best ? F(t[u].best, x) : -1e18;
if(t[u].a == t[u].b) return ans;
int ls = u << 1, rs = ls | 1;
if(t[ls].b >= x) return max(ans, query(ls, x));
else return max(ans, query(rs, x));
}

小优化

如果是线段全部插入后进行查询，可以通过这种方法进行优化：

  • 询问从小到大排序，线段按左端点从小到大排序，每次询问之前进行左端点在之前的操作。
  • 可以发现线段的左端点对询问没有影响。实现中，如果这条线段的右端点在线段树节点的右端点之右，就当作这条线段穿过这个节点对应的区间。

李超树合并

题目。

同样使用动态开点的方法：

void insert(int &u, int p, int l, int r)
...

然后合并：

int merge(int u, int v, int l, int r)
{
if(!u || !v) return u + v;
if(t[v].best) insert(u, t[u].best, l, r);
if(l == r) return u;
int mid = l + r >> 1;
t[u].ls = merge(t[u].ls, t[v].ls, l, mid);
t[u].rs = merge(t[u].rs, t[v].rs, mid + 1, r);
return u;
}

也就是要在合并前加入另一棵线段树的优势线段。

对于插入直线和一般的不重复合并的要求，时间复杂度在第一篇题解中被证明为 \(O(n\log n)\)。

优化 DP

比如这道题，容易得出 DP 方程 \(f_i=\max\Big\{T_jT_i+\dfrac{f_j}{2}-F_j\Big\}\)，令 \(k=T_j,b=\dfrac{f_j}{2}-F_j,x=T_i\)，则转化为动态加入直线求最大值，时间复杂度 \(O(n\log n)\)，常数和代码难度远小于平衡树。

一般来说要对式子进行转化，比如把只与 \(i\) 有关的项弄到 \(\min\) 外，提取与 \(i\) 有关的因式，即把式子化为 \(f_i=A_i+B_i\min\big\{P_jC_i+Q_j\big\}\)。

CDQ 分治

思想

对于一类由前往后计算贡献的题目，分为两部分，分别计算左右两部分内部的贡献，然后计算做部分对又部分的贡献。多用于偏序问题。

二维偏序

类似于归并排序。

三维偏序（动态二维数点等）

以第一维为第一关键字由小到大排序，分治过程中按第二维进行归并排序，双指针扫描第二维，用树状数组维护当前加入点的第三维的前缀和。

注意，有时候可能退出来多维的偏序，但可能是可以优化掉一维的。

动态逆序对。

动态插入、查询最小曼哈顿距离。

路灯（转化为三维偏序）。

四维转三维。

优化 DP

注意调用顺序，先计算左部分的所有 DP 值，再计算左部分对右部分的贡献，最后计算右部分的 DP 值，这样才能保证无后效性。

三维偏序状态 DP。

[ARC159F] Good Division。

分治。

数位 DP

本质是分段。

做题时首先思考前导零是否影响答案。

主要有记忆化搜索和循环两种写法：

  • 记忆化搜索：函数定义 dp(int pos, int limit, int lead, ...)，表示当前讨论到前 \(pos\) 位，是否受高位限制，是否是前导零，以及其它的信息。边界是 \(pos=0\)，只有一个数的时候，只有 \(limit=0,lead=0\) 才可以使用记忆化数组。不同询问记忆化数组不需要清空。
  • 循环：先预处理从 \(0\) 到 \(10^k-1\) 的情况，然后从上往下，对每一位每举这位的数小于这一位的值，表示这一位之前的都是取满的，这一位后面的随便取。注意这里没有枚举到 \(n\)，枚举到 \(0\)。如果要考虑前导零，枚举位数和首位，同时最高位不能为 \(0\)。

一般来说，记忆化搜索比较好写，循环用时少。

从低位往高位计算贡献

一般的记忆化搜索都是从高位递归到低位计算贡献，但有时候要考虑由低位加上一个高位的答案，如 恨 7 不成妻、数数。

减少状态

完美数利用 \(lcm\) 减少状态。
淘金利用数位乘积数量少减少状态。
Umnozak利用 digit-product 数量和 self-product 小于 \(10^{18}\) 减少状态。
众数中需要进行 DP 的状态是划分数，用哈希表避免重复计算本质相同的状态。

维护算法过程

完美消除的“求解消除次数问题”可以用单调栈解决，用状压维护单调栈。
LIS 数用状压维护二分数组。

运算

可以有位运算和加减运算。位运算比较自然，直接按模板弄即可。加减运算按二进制进行，从高往低讨论，记录当前讨论过的位的值，一般，如果这个值小于某个值，则没有可能合法；如果大于某个值，则一定合法，所以状态数量在一个比较小的范围内。

数对。
Zhu的数学问题。

分治（整体二分）优化 DP

用于决策单调性的 DP。

决策单调性

对于 \(f_i=\max/\min w\left(i,j\right)\)，设 \(f_i=w\left(i,k_i\right)\)，如果对于 \(i_1<i_2\)，\(k_{i_1}\leq k_{i_2}\)，则具有决策单调性。下面以取最小值为例。

性质 1

如果对于 \(i_1<i_2,j_1<j_2,w\left(i_1,j_1\right)\leq w\left(i_1,j_2\right)\) 满足 \(w\left(i_2,j_1\right)\leq w\left(i_2,j_2\right)\)，则具有决策单调性。

证明：

假设不具有决策单调性，即存在 \(i_1<i_2,k_1>k_2\)。

则有 \(w(i_1,k_1)<w(i_1,k_2),w(i_2,k_1)>w(i_2,k_2)\)，与条件矛盾。

性质 2

如果对于所有 \(i_1\leq i_2,j_1\leq j_2\)，都有 \(w(i_1,j_1)+w(i_2,j_2)\leq w(i_1,j_2)+w(i_2,j_1)\)，则满足决策单调性。

证明：

假设存在 \(i_1<i_2,j_1<j_2\)，满足 \(w(i_1,j_2)<w(i_1,j_1),w(i_2,j_2)>w(i_2,j_1)\)，则 \(w(i_1,j_1)+w(i_2,j_2)> w(i_1,j_2)+w(i_2,j_1)\)，矛盾，所以根据性质 1，满足决策单调性。

可以通过证明 \(w(i_1,j_2)-w(i_1,j_1)\leq w(i_2,j_2)-w(i_1,j_2)\)（即增量单调）证明决策单调性。

几个证明

数列切割

由增量单调证明性质 2 中式子。

白菜距离

如图，假设 \(A\) 的最优决策点为 \(P\)，\(B\) 的最优决策点为 \(Q\)，\(B\) 在 \(A\) 顺时针方向，\(Q\) 在 \(P\) 逆时针方向。

则 \(AP>AQ,BQ>BP\)，所以 \(AP+BQ<AQ+BP\)，与 \(AQ+BP\ge AP+BQ\) 矛盾。

灯塔

可以根据图像证明增量。也可以两边平方，注意保证两边符号都是正。

实现

采用整体二分，solve(l,r,L,R) 表示状态在区间 \([l,r]\)，决策点在区间 \([L,R]\)，枚举状态区间的中间点的所有决策点转移进行分治，时间复杂度 \(O(n\log n)\)。

有时贡献不好计算，考虑计算增量，通过类似莫队的方式移动左右指针转移。如果不支持删除，可以通过这样的步骤保证正确性和时间复杂度：

  1. 初始时，区间为整个序列。
  2. 右指针从状态区间的右端点移动到中间点。
  3. 左指针从决策区间的左端点向右移动，并记录结果和最优决策点。
  4. 回滚第 3 步的操作，分治左部分。
  5. 回滚第 2 步的操作，把右端点移到中点的最有决策点，分治右部分。
  6. 回滚第 5 步的操作，此时区间为整个序列，与原来相同。

左右端点的移动都是 \(O(n\log n)\)，所以时间复杂度 \(O(n\log n)\)。

斜率优化 DP

维护凸包

只考虑加入 \(x\) 递增的点。

以下凸包为例，如果新连边的斜率小于等于最后一条边的斜率，则弹出最后一个点，加入这个点。

优化 DP

式子化简

对于形如 \(f_i=\min/\max_{j=0}^{i-1}a_ib_j+c_i+d_j\) 的式子，另 \(j\) 为最优决策点，化为 \(d_j=-a_ib_j-c_i+f_i\)，令 \(y=d_j,x=b_j,k=-a_i,b=f_i-c_i\) 则这个式子是斜截式，要求最大化或最小化斜率。

凸包方向

最大化上凸包，最小化下凸包。

查询答案

  • \(k,b\) 递增（当最大化，\(k\) 应递减）：单调队列，具有决策单调性，如果开头两个点的斜率大于当前的 \(k\)，则弹出队首，此时队首是最优决策点。
  • \(b\) 递增：二分第一个斜率大于 \(k\) 的线段。
  • 都不递增
  • 李超线段树。
  • CDQ 分治的 \(O(n\log^2n)\) 做法：分治左区间，把左区间按 \(x\) 排序，构建凸包，右区间二分求解，递归右区间，按 \(x\) 归并排序。
  • CDQ 分治的 \(O(n\log n)\) 做法：先按 \(k\) 排序，分治前按下标划分区间，注意此时两个区间的 \(k\) 都应有序，可以先用 nth_element 求第 \(mid-l+1\) 小，再进行划分，分治左区间，用单调队列构建凸包并计算对右区间贡献，按 \(x\) 归并排序。
  • 二进制分组：只是用来维护动态凸包。
  • 平衡树：暂无，用来维护动态凸包。

效率对比：

无特殊声明，上面都没有快读，非递归函数加 inline 优化。

决策单调性

四边形不等式

反方向四边形不等式

四边形不等式与区间 DP

分治法（整体二分）

分治法与增量计算贡献

二分队列

二分栈

优化区间 DP

序列划分

路径交错

动态 DP

序列——线段树维护矩阵转移

首先，我们需要普通 DP 方程改为矩阵乘法或广义矩阵乘法形式，可能会增加一些状态，然后用线段树维护矩阵乘法即可。

这个模型推荐使用横向量乘方阵的形式，可以直接从左往右乘。

树——重链剖分

原理

首先，记录每个节点的轻儿子对这个节点 DP 数组的贡献，然后用线段树维护一条重链。

对于一条重链，链底（一定是叶子节点）的矩阵一般是单位阵，其它节点的矩阵表示一个状态转移，初始的向量是一个关于链底的向量，用这个向量乘一个后缀之后，得到这个后缀开头节点的完整 DP 信息。

对于修改的节点，需要修改的有：

  • 这个节点。
  • 到根节点的轻边，轻边上父节点。

实现细节

修改时不可能直接求节点轻儿子对它的贡献，所以考虑增量，这就要求维护前后的两个 DP 信息，具体如下：

  • 求当前链顶的信息。
  • 进行上一个修改（当前节点的修改）。
  • 求当前链顶信息。
  • 用增量改变链顶的父节点的信息。
  • 当前节点条到链顶的父节点。
  • 当链顶节点为根，修改当前节点。

建议使用方阵乘列向量的方式，线段树维护时可以从左往右乘，但查询时要先查询右儿子，再查询左儿子。

卡常

  • 对每条重链开线段树。
  • 矩阵乘法循环展开，使用数组存矩阵，但注意 memset 的空间需要是一个具体矩阵的空间（而不是传的指针）。
  • inline，快读。

参考代码（P4751）

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5, INF = 1e9;

int n, m, x[N];
int la[N], ne[N * 2], en[N * 2], idx;
int fa[N], dep[N], size[N], son[N], top[N], End[N], id[N], rnk[N], dfst;
int g[N][2], f[N][2];
struct node{
int l, r;
int x[2][2];
}t[N * 4];
int root[N], pid;

inline void init(int x[][2])
{
x[0][0] = x[1][1] = 0;
x[0][1] = x[1][0] = -INF;
}
inline void init(int x[][2], int g[])
{
x[0][0] = x[0][1] = g[0];
x[1][0] = g[1], x[1][1] = -INF;
}
inline void init(int p[], int u)
{
p[0] = 0, p[1] = x[u];
}
inline void mul(int a[][2], int b[][2], int c[][2])
{
static int t[2][2];
t[0][0] = max(a[0][0] + b[0][0], a[0][1] + b[1][0]);
t[0][1] = max(a[0][0] + b[0][1], a[0][1] + b[1][1]);
t[1][0] = max(a[1][0] + b[0][0], a[1][1] + b[1][0]);
t[1][1] = max(a[1][0] + b[0][1], a[1][1] + b[1][1]);
c[0][0] = t[0][0];
c[0][1] = t[0][1];
c[1][0] = t[1][0];
c[1][1] = t[1][1];
}
inline void mul(int a[][2], int b[], int c[])
{
static int t[2];
t[0] = max(a[0][0] + b[0], a[0][1] + b[1]);
t[1] = max(a[1][0] + b[0], a[1][1] + b[1]);
c[0] = t[0];
c[1] = t[1];
}

void build(int &u, int a, int b, int eid)
{
u = ++ pid;
if(a == b) return a == eid ? init(t[u].x) : init(t[u].x, g[rnk[a]]);
int mid = a + b >> 1;
build(t[u].l, a, mid, eid), build(t[u].r, mid + 1, b, eid);
mul(t[t[u].l].x, t[t[u].r].x, t[u].x);
}
void modify(int u, int x, int g[], int a, int b, int eid)
{
if(a == b) return a == eid ? init(t[u].x) : init(t[u].x, g);
int mid = a + b >> 1;
if(x <= mid) modify(t[u].l, x, g, a, mid, eid);
else modify(t[u].r, x, g, mid + 1, b, eid);
mul(t[t[u].l].x, t[t[u].r].x, t[u].x);
}
inline void query(int u, int g[])
{
mul(t[u].x, g, g);
}

inline void add(int a, int b)
{
ne[ ++ idx] = la[a];
la[a] = idx;
en[idx] = b;
}
void dfs1(int u, int f)
{
fa[u] = f, dep[u] = dep[f] + 1, size[u] = 1;
for(int i = la[u]; i; i = ne[i])
{
int v = en[i];
if(v != f)
{
dfs1(v, u);
size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
}
}
void dfs2(int u, int ft)
{
top[u] = ft;
rnk[id[u] = ++ dfst] = u;
if(son[u])
{
dfs2(son[u], ft), End[u] = End[son[u]];
g[u][0] = 0, g[u][1] = x[u];
for(int i = la[u]; i; i = ne[i])
{
int v = en[i];
if(v != fa[u] && v != son[u])
{
dfs2(v, v);
g[u][0] += max(f[v][0], f[v][1]);
g[u][1] += f[v][0];
}
}
f[u][0] = g[u][0] + max(f[son[u]][0], f[son[u]][1]);
f[u][1] = g[u][1] + f[son[u]][0];
}
else End[u] = u, g[u][1] = f[u][1] = x[u];
if(u == ft) build(root[u], id[u], id[End[u]], id[End[u]]);
}

inline int modify(int u, int y)
{
static int p[2][2], f1[2], f2[2];
g[u][1] += y - x[u];
init(p, g[u]);
int t = 1;
while(top[u] != 1)
{
int v = top[u], w = fa[v];
init(f1, End[u]);
query(root[v], f1);
if(t) x[u] = y, t = 0;
modify(root[v], id[u], g[u], id[v], id[End[v]], id[End[v]]);
init(f2, End[u]);
query(root[v], f2);
g[w][0] += max(f2[0], f2[1]) - max(f1[0], f1[1]);
g[w][1] += f2[0] - f1[0];
u = w;
}
if(t) x[u] = y;
modify(root[1], id[u], g[u], id[1], id[End[1]], id[End[1]]);
init(f1, End[1]);
query(root[1], f1);
return max(f1[0], f1[1]);
}

int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ ) scanf("%d", &x[i]);
for(int i = 1; i < n; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs1(1, 0), dfs2(1, 1);
int ans = 0;
while(m -- )
{
int x, y;
scanf("%d%d", &x, &y);
x ^= ans;
printf("%d\n", ans = modify(x, y));
}
return 0;
}