P4563 [JXOI2018]守卫
zxy 讲过。
如果直接从代数角度推推不出来，从几何角度会好一点。首先最后一个位置一定要放，放完之后有一些点可以被看到，假设为 \(p_{1\sim k}\)，那么序列实际上被 \(p_{1\sim k}\) 分成了若干个相互独立的段，每段不会影响到其它的段。对于一段，可以选择是否选右端点，所以它的贡献就是 \(\min(f_{p_{i}+1,p_{i+1}},f_{p_i+1,p_{i+1}-1})\)。枚举 \(r\) 然后转移可以做到 \(\mathcal{O}(n^2)\)。
启示：从几何角度观察性质。
CF573E Bear and Bowling
Description
给定长度为 \(n\) 的序列 \(a_{1\sim n}\)，求 \(a\) 的一个子序列 \(b\)，最大化 \(\sum\limits_{i=1}^m ib_i\)。
Analysis
平方的 DP 是显然的。设 \(f_{i,j}\) 表示当前在 \(i\)，之前选了 \(j\) 个最优权值。容易得到转移：
\[f_{i,j}=\max(f_{i-1,j},f_{i-1,j-1}+j\cdot a_i) \]发现这是一个类似 \((\max,+)\) 卷积的东西。但是 \(f_{i,j}\) 看起来并不凸。所以感觉优化是行不通的，必须找性质。
发现选正的是不劣的，考虑钦定选所有正的之后选负的。这样问题变成了类似最小化 \(\sum ib_i+val_i\) 的东西。比较好的一点在于 \(b_i\) 全都是正的了，但是没有性质依赖这个转化仍然难以发挥。
考虑做一些 exchange argument，发现一个序列中最先选的一定是最大值，猜想是从大到小选。但是发现如果两个数不相邻的话难以进行调整（插句嘴，这里我调整的时候采用了这样一个逻辑：若一个序列中 \(i\) 选了但是 \(j\) 没选，什么时候交换 \(i,j\) 更优秀，如果交换更优秀了但是 \(i\) 仍然选择了，就意味着 \(j\) 一定会被选择，这样就构成了选择之间的依赖关系）。考虑这样一个过程，选最大值之后，两边区间一定也是最大值优先，左边的贡献是 \(a_l+mx\)，右边的贡献是 \(a_j+a_j\)，可以发现一件事情，就是如果 \(i\) 更大的话左边铁优了，这个讨论扩展到中间有更多数的时候也是成立的，所以对于 \(j\) 来说，如果 \(j\) 被选择且 \(i<j,a_i>a_j\)，则 \(i\) 铁被选择。进一步讨论的话可以发现我们只要确定后缀最小值就可以确定整个子序列。但是次数的限制依然存在，难以通过 DP 等方式求解。
由于上面的限制其实不紧，我一直尝试得到更强的结论，但是得到的结论都失去了简洁性。不会了。
Solution
一个结论是，假设 \(f_{i,j}\) 对应的下标集合为 \(F_{i,j}\)，那么 \(F_{i,j}\) 是在 \(F_{i,j+1}\) 的基础上恰好加上一个数得到的。这等价于包含 \(i\) 的 \(F_{i,j}\) 恰好为一个后缀。可以这么猜，如果数量越少，那么对元素的筛选就越严格，那么
证明考虑画出转移网络，只需要不存在 \(F_{i-1,j}\) 转移到 \(F_{i,j+1}\) 且 \(F_{i-1,j+2}\) 转移到 \(F_{i,j+2}\) 的情况就好了。考虑归纳证明，\(F_{i-1,j}\) 为 \(S\)，\(F_{i-1,j+1}\) 为 \(\{S,x\}\)，\(F_{i,j+2}\) 为 \(\{S,x,y\}\)，\(F_{i,j+1}\) 为 \(\{S,i\}\)。注意到根据前面的结论，集合中的数按照优先级构成一个全序，且 \(x\) 优于 \(y\)。可以得到。
- \(x>y\)，注意到这样转移有 \(\{S,i\}>\{S,x\}\)，前面分别插入一个 \(x,y\) 可以得到 \(\{S,x,i\}>\{S,y,x\}\)，矛盾了。
- \(x<y\)，仍然有 \(\{S,i\}> \{S,x\}> \{S,y\}\)，前面插入一个 \(x\) 有 \(\{S,x,i\}>\{S,x,y\}\)，仍然矛盾。
所以可以每次加入增量最大的元素来维护。问题转化成维护一些一次函数 \(k_ia_i+b_i\)，支持：
- 区间 \(k_i\) 加一。
- 区间 \(b_i\) 加 \(a_i\)。
- 查询一次函数最大值。
polylog 不太好做，而维护直线是分块的经典应用场景。套用分块可以做到单根号。
当然，据此还可以观察到，DP 过程中每次下标集合加入 \(i\) 的是一个后缀，所以可以平衡树维护插入结点，区间加等差数列的操作，复杂度一个 \(\log\)。
Conclusion
感觉这种东西只能靠猜或者打表啊。贪心的常见套路推导有 exchange argument 和临项交换等等，但是更多的时候需要敏锐的性质观察和瞎猜。这个性质的切入点有对 DP 打表，或者尝试从最大值开始构造，我尝试了后者但是用来 exchange argument 了，没有注意到可能可行的结论，感觉观察 DP 数组更加可行的样子（？）。
不过值得注意的是，上面的推导根本没有用到权值函数的性质，也就是说这个性质，即增量的性质在问题中是常见的。
关于这个问题和凸性的关系，我暂时没有什么头绪。
P5576 [CmdOI2019]口头禅
Description
给定 \(n\) 个字符串，求区间 \([l,r]\) 内所有串的最长公共子串。
Analysis
建立广义 SAM。考虑分治，转化到树上就是求深度最大的结点使得它的子树里面有每个串中的结点。考虑猫树分治，建立当前分治区间的虚树，显然对于一个结点我们只关注它子树内右边区间内最长的前缀和左边区间内最长的后缀。这个容易用线段树合并维护。时间 \(2\log\)，空间有点大。
Solution
上面的做法其实可以不用猫树分治，直接启发式合并维护连续段，然后扫描线做二维数点可以做到相同复杂度。
下面有两种基于根号结论的做法：
第一种做法是，仍然考虑猫树分治。经典的求最长公共子串的方法是，对每个串建立 SAM，将最小串在上面匹配，并求出每个右端点匹配最长的区间长度。可以想到分治的时候以分治中心建立 SAM，但是分治中心可能长度很大，我们需要将分治中心的长度限制在和最短串有关的范围内，可以考虑倍增，设当前最短串的长度为 \([2^x,2^{x+1})\)，那么在这些串之中找到中间串，并两边分治。
有关复杂度分析，假设字符串总长为 \(n\)，每个阈值最多递归 \(\log\) 层，最多 \(\log\) 个阈值，所以复杂度是 \(\mathcal{O}(n\log^2n)\) 的。
然后套用求 LCS 的做法就好了。查询的时候只要 \(\mathcal{O}(|s|)\) 归并两个前缀最小值数组并求最大值就好了。如果使用记忆化，复杂度是至多是 \(\mathcal{O}(q|s|)\) 的，但是字符串个数可能凑不够 \(q\)，如果个数小于 \(\sqrt{n}\) 的话，假设个数是 \(x\)，复杂度最高 \(x^2\cdot\dfrac{n}{x}=nx\leq n\sqrt{n}\)，如果个数大于 \(\sqrt{n}\)，那么 \(|s|\) 长度是有保证的。
还有一种扫描线做法。一个结论是，如果将所有串建立广义 SAM，那么每个结点子树颜色总和是 \(n\sqrt{n}\)。考虑一个串的贡献，它的每个子串最多贡献 \(1\) 的贡献，贡献和是 \(|s|^2\) 的，众所周知 \(\sum|s|^2=n\sqrt{n}\)。
所以每次加入一个颜色然后暴力维护答案就好了。
Conclusion
cmd 讲了两个结论。一个是复杂度为 \(\min(S_x,S_y)\) 的记忆化查询是根号级别的，第二个是广义 SAM 上颜色数级别的结论。所以说复杂度分析还是 DS 中挺重要的一环啊。另外我最喜欢的其实是那个倍增，第一，倍增让选定串和最小值大小同阶，第二，倍增区间的段数是 \(\mathcal{O}(\log n)\) 级别的，两个都是相当强的性质。
P4217 [CTSC2010]产品销售
Analysis
可以建立费用流模型，唯一比较困难的是延迟的问题，稍加尝试可以得到如下模型：
- \(S\) 向每个点连边 \((U_i,P_i)\)。
- 每个点向 \(T\) 连边 \((D_i,0)\)。
- \(i\) 向 \(i+1\) 连边 \(C_i\)。
- \(i+1\) 向 \(i\) 连边 \(M_i\)。
直接流可以有 \(30\) 分。
考虑套用 UOJ#455 的套路，利用增量-最小费用任意流模型。分析会有哪些流：
- 第 \(i\) 个季度补前面的订购量。
- 前面的季度补 \(i\) 的订购量。
- \(i\) 替代前面的流，分为有/无退流。
讨论一下这几种流的关系。第一种流会加一个没退流的第三种。第二种流会加一个有退流的第三种，第三种会加一个第二种。用两个堆维护一下就好了。这样可能会被卡到 \(\mathcal{O}(f\log n)\)，不能通过。
Solution
考虑线段树模拟费用流，先把上面加一排点，然后从 \(1\to n\) 考虑增广下面的边。如果从前面增广过来，那么会出现一个从后往前方向的反边，但事实上我们不会用到这些反边，因为用了这些反边就到不了了。如果从后面增广过来，那么会出现从前往后的反边，这些边可能参与退流。所以我们要做的操作实际上是：
- 查询从前往后的权值最小值。
- 查询从后往前的权值最小值。
- 维护退流流量，并同时维护每个边的权值。
可以开三棵线段树 \(s_1,s_2,s_3\)，分别维护当前位置 \(i\) 到前面每个点的权值，到后面每个点的权值，和从前往后增广的流量。操作相当于：
- 扫描线的时候在前两棵树上做区间加。维护区间最小值。
- 在第三棵树上做区间加，区间减，维护区间最小值，注意需要维护反边流量和边权。
区间加和维护区间最小值是平凡的，关键是维护边权，只有那些用完了流量的反边才有可能边权改变，并且我们发现，如果一个反边被用了之后，它之后就再也不会成为反边，所以边权变化总和是 \(\mathcal{O}(n)\) 的，可以使用线段树暴力修改。总时间复杂度是 \(\mathcal{O}(n\log n)\) 的。
启示：实践证明所谓增量-最小费用任意流的应用场景是不如线段树模拟费用流的，因为它的增广可能涉及到源点和汇点，路径较为复杂。这类问题的模型是比较复杂的，需要多做，总结套路。
AGC018C Coins
Analysis
建立费用流模型，每个点向三个队伍连边。
考虑优化找增广路的过程，容易发现最后增广路会依次经过三个点之中的若干个点，考虑维护堆 \(q_{i,j}\) 表示从 \(i\) 走到 \(j\) 的所有边的权值，每次只要维护每个人的从属即可。找最短路可以直接 dfs。
P4480 [BJWC2018]餐巾计划问题
Solution
这个问题有着太多的解释，一周前我写了一个根据上下界网络流，以钦定思路推导的方法，这里再将一种思路。
我们需要保证每天最后都有 \(r_i\) 条毛巾，但是却不希望它流到汇点而损耗，怎么办呢？可以在这些流量流出汇点之后，从源点补 \(r_i\) 的流量，可以想象这些流量流到汇点之后又流了回来。所以建立如下模型：
- 拆两排点，表示干净毛巾和脏毛巾。
- \(S\) 向 \(i_0\) 连边 \((\inf,p)\)。
- \(i_0\) 向 \(T\) 连边 \((r_i,0)\)。
- \(S\) 向 \(i_1\) 连边 \((r_i,0)\)。
- \(i_1\) 向 \(i_0+m\) 和 \(i_0+n\) 连边，表示洗了。
关于怎么优化到 \(\mathcal{O}(n\log n)\)。考虑三分流量，也就是买的餐巾数量，如果确定了这个尝试找到一个贪心做法。显然我们希望尽可能用慢洗，但是在一个位置我们并不能很好地确定它是慢洗还是快洗，但是我们其实没必要立即决定这个问题，可以先把这些餐巾挂在这里，等到需要的时候再决定。那么在需要的时候，我们优先买，再考虑所有毛巾中可以慢洗的毛巾，再考虑能够快洗的尽可能晚的毛巾（因为早的可以过渡到慢洗）。
Conclusion
利用费用流凸性引出一个贪心，在任意流问题中，三分可以给问题增加条件，有时能获得意想不到的效果。贪心的过程也是用到了一个常见的技巧：延迟决策，如果一些决策不好确定或者维护，可以等到需要它的时候再用，这个技巧在 DP 中也比较常见。
另外记住这个结论的加强版，就是如果一条边连接了 \(V-\{s,t\}\) 的两个联通块，那么最后的费用关于这条边的流量是凸的。
「Lydsy1708 月赛」跳伞求生
Solution
动态加点的做法略过，这里讲一种维护凸函数的做法。
首先费用流模型是显然的，并且模型是一条单向链。考虑从前往后维护 \(f_{i,j}\) 表示第 \(i\) 条边流量为 \(j\) 的时候，前面的代价最小值，那么考虑两个事件：加入一条从源点过来的代价为 \(x\) 的边，加入一条流向汇点的代价为 \(x\) 的边。
如果加一条从源点过来的代价为 \(x\) 的边，那么流量会增加，转移是：
\[f_{i,j}=\max(f_{i-1,j},f_{i-1,j-1}+x) \]容易发现会成为前面 \(+x\) 的是一个后缀，那么 \(f\) 的差分数组的变化呈现这样一个形式：从中间插入一个 \(x\)，将一部分差分数组往后移，这相当于插入 \(x\) 之后排序。
如果加一条流向汇点的代价为 \(x\) 的边，那么流量会减少，转移是：
\[f_{i,j}=\max(f_{i-1,j},f_{i-1,j+1}+x) \]这个需要一些讨论，因为 \(f_{i,0}\) 是可能变化的。首先 \(x\) 影响的是一个前缀，它满足 \(f_{i-1,j+1}+x\geq f_{i-1,j}\)，也就是 \(x\geq -g_{i,j+1}\)，分两种情况，如果 \(j=0\) 的情况不满足，这样整个 \(f\) 数组不会改变，可以忽略。如果 \(j=0\) 的情况满足，\(f_{i,0}\gets f_{i,1}+x\)，整个差分数组往前移动一位，并插入一个 \(-x\)。我们发现这个过程中 \(g_{i,1}\) 没掉了，所以相当于插入一个数，删除一个数。
最后的答案就是 \(f_{i,0}\)。
Conclusion
说实话这种做法更像是做了一个 DP 优化。对于一个凸的 DP 数组，利用其性质，使用合适的数据结构维护这个凸函数，一般常见的手法是用平衡树等结构维护其差分数组。
最近看了下《浅谈 OI 中的费用流问题》，但是感觉有些部分还是有点模糊，等以后学了更多东西再来补个笔记吧。
标签：11,一个,可以,复杂度,区间,mathcal,日志,维护,2022.1 From： https://www.cnblogs.com/yllcm/p/17044965.html