杂项全家桶

· · 个人记录

二分队列

这玩意浪费了我12h。

考虑设 f_T 表示坐 T 号列车刚到终点时的最小花费，将 T 按照发车时间 a 排序，则有：

f_{T}=T.cost+\min_{M.y=T.x,M.b\leq T.a}(f_M+price_{T.x}\times Query(M.b,T.a))

其中 Query(L,R) 表示 \sum_{k}[[l_i,r_i]\sube(L,R)]。

注意到 \min 里面的东西具有决策单调性：将 M 按照下车时间 b 排序，当 T_1<T_2 时，设 f_{T_1} 由 M_x 转移，f_{T_2} 由 M_y 转移，则有 x\leq y。

（T.a 从 a_1 增加到 a_2 的过程中，所有决策点 M 的代价都增加了 price_{T.x}\times Query(a_1-1,a_2)，相对大小不变）

对于每一个决策点，维护其作为最优决策点时 T.a 的取值区间，用队列维护。产生新决策 M' 时，在最靠后的一个取值区间 [l,r]（对应决策 M）上二分，找到满足 f(M',t)<f(M,t) 的最小的 t，使 M 的决策区间变成 [l,t-1]，M' 的决策区间为 [t,r]。加入队列。

由于询问的 T.a 单增，所以查找最优决策点时，弹出前面所有 r<T.a 的决策点即可。

而 Query 本身的值离散化后用主席树维护即可。

注意事项：

  1. 因为有 M.y=T.x 的限制，所以需要对每一个岛屿维护一个二分队列。

  3. 二分队列本身复杂度 O(n\log n)，查询 Query 的复杂度 O(\log n)，总共 O(n\log^2n)，需要大力卡常。

性质

  1. 树形dp时，如果一个节点的 f 只有 \min(sz,k) 个值是有用的，则 dp 一遍只需要 O(nk) 的复杂度。

  2. 有时题目要求维护的东西有效期是一个区间，那么可以考虑在时间轴升序的过程中模拟/整活。例えば：CSP-S 2024 T4，this

长链剖分

如果要维护的dp方程为 f_{v,k}\leftarrow f_{son,k+1}，即信息均以绝对深度为下标，则可以通过长链剖分达到 O(n) 的复杂度。

具体地，每次将深度小的子树向深度大的子树合并。因为一条长链只会在链首完成一次合并，而所有长链的长度和为 n，所以总长就是 O(n)。

2-SAT

考虑将一个变量 p 拆成两个点 p 和 \neg p。一条边 p\rightarrow q 表示如果 p 成立，q 一定也成立。连了 p\rightarrow q 一定也要把 \neg q\rightarrow \neg p（逆否命题）连上，虽然我还不知道为什么。

如果 p 可达 \neg q，则 p 只能取 False。如果 \neg p 可达 q，则 p 只能取 True。如果互相可达，没救了。否则都行。

可达性可以缩SCC后看拓扑序。

可持久化线段树

怎么维护一个支持区间加、区间求和、区间复活的可持久化线段树。正经的主席树是单点加、区间求和，全局复活。先考虑做出来单点加。

考虑对于每个节点维护一个 lazytag，pushdown 的时候将左右儿子都复制一个新的出来，下传到新的节点上。

然后是区间复活。找到要复活的版本，把该版本需要复活的 \log 个节点 copy 出来，把当前版本对应的 \log 个节点直接改成复活节点的样子就可以。

点减边容斥

如果题目描述了一个函数 f([l,r])，要求我们得出序列上每一个区间 f([l,r]) 的值之和，但是我们只能得到 g([l,r])=\sum_{[l',r']\supe[l,r]} f([l',r']) 的话，考虑怎么容斥。

考虑得出 \sum g({i})，那此时每一个长度 \geq 2 的区间 [l,r] 被算了 r-l+1 次，需要减掉 r-l 次。那可以再减去 \sum g([i,i+1])，此时正好就对了。

wqs 二分

F 题放 wqs 二分板子，喜欢我们 Educational Round 吗。

设原序列已经有 c 个 docker 了。则我们可以分别得到最多两个备选的 docker 数量 c_1\leq c\leq c_2，最优解一定在 c_1 或 c_2 取到。达到 c_1 只需要破坏 docker，故 c_1 的答案为 c-c_1。难点在于计算 c_2 的答案。

我们可以设 f_i 表示在 [i,i+6) 上创建出一个 docker 的修改次数。然后容易得到一个 O(nc_2) 的 dp。设 g_{i,j} 表示在 [1,i] 上创建 j 个 docker 所需的最少修改次数，则有：

g_{i+1,j}\gets g_{i,j}\qquad g_{i+6,j+1}\gets g_{i,j}+f_{i+1}

注意我们其实只需要 g_{n,c_2}， 且若设 h(x)=g_{n,x}，则 h(x) 是单增且下凸的，所以可以直接进行 wqs 二分。

具体地，二分一个斜率 k，转为求 h(x)-kx 的最小值。在 dp 中的意义是，每做出一个 docker 可以额外赠送 k 个修改次数。此时不需要记录做了多少个 docker，故第二维可以省略：

h_{i+1}\gets h_i\qquad h_{i+6}\gets f_{i+1}-k

转移的时候同时记录做了多少个 docker，这样做完一遍 dp 可获得一个二元组 (cost,cnt) 分别表示消耗的修改次数（可以是负数）和做出来的 docker 数量。若 cnt<c_2，代表取到 c_2 的 k 更大，反之更小。直接二分即可。

但是多点共线的时候有概率挂掉。我们在二分过程中用每一个 k 得到的一对 (cost,cnt) 都可以算出一个 h(cnt)=cost+k\cdot cnt。共线时，h(c_2)=cost+k\cdot c_2。因为 h 是下凸壳，这个计算出来的答案只会 \leq 真实值。直接取 \max 即可得到真实值。

凸包闵可夫斯基和分治优化dp

以下所有凸包不妨全认为是下凸。

两个凸包 f,g 的闵可夫斯基和 h(i)=\min_k\big(f(k)+g(i-k)\big) 可以在 O(|f|+|g|) 的复杂度内求得，且 h 同样为凸包。设 \Delta f,\Delta g 为 f 和 g 的差分序列，则 h(i) 本质上是要在其上选择两个长度和为 i 的前缀，使得求和后最小。因凸性，\Delta f 和 \Delta g 均单调不减，直接贪心（归并）选择就是对的。具体来说：

vector<int> Conv(const vector<int> &f,const vector<int> &g){
    vector<int> h; int p1=0,p2=0;
    while(p1<f.size()&&p2<g.size()){
        h.push_back(f[p1]+g[p2]);
        if(p1==f.size()-1) p2++;
        else if(p2==g.size()-1) p1++;
        else (f[p1+1]-f[p1]<g[p2+1]-g[p2]?p1++:p2++);
    }
    return h;
}

若一转移 f_i(j)=\min_k(f_{i-1}(k),w_{i}(j-k))，其中 w_i 均为凸函数，直接操作可能是 O(n\sum|w_i|) 的。但是这是凸包连加，若化为 f_{[l,r]}=f_{[l,m]}\circ f_{[m+1,r]}（其中 m=(l+r)/2，\circ 是求闵可夫斯基和），分治递归下去即为 O\Big(\sum |w_i|\log n\Big) 。

这个操作和求一次函数连乘（分治，O(n\log^2n)）相似。

记 h_i 表示在 [i,i+L) 上做出来一个 MOO 的花费，然后设 f_{[l,r],x\in[0,2],y\in[0,2]}(i) 表示区间 [l,r] 中，左边空出 x 个格子，右边空出 y 个格子，做出至少 i 个 MOO 的最小花费。转移时枚举 m 是 MOO 的哪一位（或者根本不在这里放 MOO），闵可夫斯基和后直接取 \min 即可。复杂度 O(L^2n\log n)，因为对于长度为 len 的区间来说，其上的凸包长度只有 \lfloor len/L \rfloor。