专栏文章

杂项全家桶

aabv3Rpkg
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miql95w8
此快照首次捕获于
2025/12/04 06:38
3 个月前
此快照最后确认于
2025/12/04 06:38
3 个月前
查看原文

二分队列

这玩意浪费了我12h。
考虑设 fTf_T 表示坐 TT 号列车刚到终点时的最小花费，将 TT 按照发车时间 aa 排序，则有：
fT=T.cost+min⁡M.y=T.x,M.b≤T.a(fM+priceT.x×Query(M.b,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)Query(L,R) 表示 ∑k[[li,ri]⊆(L,R)]\sum_{k}[[l_i,r_i]\sube(L,R)]。
注意到 min⁡\min 里面的东西具有决策单调性：将 MM 按照下车时间 bb 排序，当 T1<T2T_1<T_2 时，设 fT1f_{T_1} 由 MxM_x 转移，fT2f_{T_2} 由 MyM_y 转移，则有 x≤yx\leq y。
（T.aT.a 从 a1a_1 增加到 a2a_2 的过程中，所有决策点 MM 的代价都增加了 priceT.x×Query(a1−1,a2)price_{T.x}\times Query(a_1-1,a_2)，相对大小不变）
对于每一个决策点，维护其作为最优决策点时 T.aT.a 的取值区间，用队列维护。产生新决策 M′M' 时，在最靠后的一个取值区间 [l,r][l,r]（对应决策 MM）上二分，找到满足 f(M′,t)<f(M,t)f(M',t)<f(M,t) 的最小的 tt，使 MM 的决策区间变成 [l,t−1][l,t-1]，M′M' 的决策区间为 [t,r][t,r]。加入队列。
由于询问的 T.aT.a 单增，所以查找最优决策点时，弹出前面所有 r<T.ar<T.a 的决策点即可。
而 QueryQuery 本身的值离散化后用主席树维护即可。
注意事项：
  1. 因为有 M.y=T.xM.y=T.x 的限制，所以需要对每一个岛屿维护一个二分队列。
  2. TT 需要以 aa 单增的顺序转移，而 MM 却需要以 bb 单增的顺序插入队列。所以不能转移完一个 TiT_i 就把它扔到队列里。
  3. 二分队列本身复杂度 O(nlog⁡n)O(n\log n)，查询 QueryQuery 的复杂度 O(log⁡n)O(\log n)，总共 O(nlog⁡2n)O(n\log^2n)，需要大力卡常。

性质

  1. 树形dp时，如果一个节点的 ff 只有 min⁡(sz,k)\min(sz,k) 个值是有用的，则 dpdp 一遍只需要 O(nk)O(nk) 的复杂度。
  2. 有时题目要求维护的东西有效期是一个区间，那么可以考虑在时间轴升序的过程中模拟/整活。例えば：CSP-S 2024 T4，this

长链剖分

如果要维护的dp方程为 fv,k←fson,k+1f_{v,k}\leftarrow f_{son,k+1}，即信息均以绝对深度为下标，则可以通过长链剖分达到 O(n) 的复杂度。
具体地，每次将深度小的子树向深度大的子树合并。因为一条长链只会在链首完成一次合并，而所有长链的长度和为 nn，所以总长就是 O(n)O(n)。

2-SAT

考虑将一个变量 pp 拆成两个点 pp 和 ¬p\neg p。一条边 p→qp\rightarrow q 表示如果 pp 成立，qq 一定也成立。连了 p→qp\rightarrow q 一定也要把 ¬q→¬p\neg q\rightarrow \neg p（逆否命题）连上，虽然我还不知道为什么。
如果 pp 可达 ¬q\neg q，则 pp 只能取 False。如果 ¬p\neg p 可达 qq，则 pp 只能取 True。如果互相可达，没救了。否则都行。
可达性可以缩SCC后看拓扑序。

可持久化线段树

怎么维护一个支持区间加、区间求和、区间复活的可持久化线段树。正经的主席树是单点加、区间求和，全局复活。先考虑做出来单点加。
考虑对于每个节点维护一个 lazytag，pushdown 的时候将左右儿子都复制一个新的出来，下传到新的节点上。
然后是区间复活。找到要复活的版本，把该版本需要复活的 log⁡\log 个节点 copy 出来，把当前版本对应的 log⁡\log 个节点直接改成复活节点的样子就可以。

点减边容斥

如果题目描述了一个函数 f([l,r])f([l,r])，要求我们得出序列上每一个区间 f([l,r])f([l,r]) 的值之和，但是我们只能得到 g([l,r])=∑[l′,r′]⊇[l,r]f([l′,r′])g([l,r])=\sum_{[l',r']\supe[l,r]} f([l',r']) 的话，考虑怎么容斥。
考虑得出 ∑g(i)\sum g({i})，那此时每一个长度 ≥2\geq 2 的区间 [l,r][l,r] 被算了 r−l+1r-l+1 次，需要减掉 r−lr-l 次。那可以再减去 ∑g([i,i+1])\sum g([i,i+1])，此时正好就对了。

wqs 二分

F 题放 wqs 二分板子，喜欢我们 Educational Round 吗。
设原序列已经有 cc 个 docker 了。则我们可以分别得到最多两个备选的 docker 数量 c1≤c≤c2c_1\leq c\leq c_2，最优解一定在 c1c_1 或 c2c_2 取到。达到 c1c_1 只需要破坏 docker，故 c1c_1 的答案为 c−c1c-c_1。难点在于计算 c2c_2 的答案。
我们可以设 fif_i 表示在 [i,i+6)[i,i+6) 上创建出一个 docker 的修改次数。然后容易得到一个 O(nc2)O(nc_2) 的 dp。设 gi,jg_{i,j} 表示在 [1,i][1,i] 上创建 jj 个 docker 所需的最少修改次数，则有：
gi+1,j←gi,jgi+6,j+1←gi,j+fi+1g_{i+1,j}\gets g_{i,j}\qquad g_{i+6,j+1}\gets g_{i,j}+f_{i+1}
注意我们其实只需要 gn,c2g_{n,c_2}， 且若设 h(x)=gn,xh(x)=g_{n,x}，则 h(x)h(x) 是单增且下凸的，所以可以直接进行 wqs 二分。
具体地，二分一个斜率 kk，转为求 h(x)−kxh(x)-kx 的最小值。在 dp 中的意义是，每做出一个 docker 可以额外赠送 kk 个修改次数。此时不需要记录做了多少个 docker，故第二维可以省略：
hi+1←hihi+6←fi+1−kh_{i+1}\gets h_i\qquad h_{i+6}\gets f_{i+1}-k
转移的时候同时记录做了多少个 docker，这样做完一遍 dp 可获得一个二元组 (cost,cnt)(cost,cnt) 分别表示消耗的修改次数（可以是负数）和做出来的 docker 数量。若 cnt<c2cnt<c_2，代表取到 c2c_2 的 kk 更大，反之更小。直接二分即可。
但是多点共线的时候有概率挂掉。我们在二分过程中用每一个 kk 得到的一对 (cost,cnt)(cost,cnt) 都可以算出一个 h(cnt)=cost+k⋅cnth(cnt)=cost+k\cdot cnt。共线时，h(c2)=cost+k⋅c2h(c_2)=cost+k\cdot c_2。因为 hh 是下凸壳，这个计算出来的答案只会 ≤\leq 真实值。直接取 max⁡\max 即可得到真实值。

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

以下所有凸包不妨全认为是下凸。
两个凸包 f,gf,g 的闵可夫斯基和 h(i)=min⁡k(f(k)+g(i−k))h(i)=\min_k\big(f(k)+g(i-k)\big) 可以在 O(∣f∣+∣g∣)O(|f|+|g|) 的复杂度内求得，且 hh 同样为凸包。设 Δf,Δg\Delta f,\Delta g 为 ff 和 gg 的差分序列，则 h(i)h(i) 本质上是要在其上选择两个长度和为 ii 的前缀，使得求和后最小。因凸性，Δf\Delta f 和 Δg\Delta g 均单调不减，直接贪心（归并）选择就是对的。具体来说：
CPP
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;
}
若一转移 fi(j)=min⁡k(fi−1(k),wi(j−k))f_i(j)=\min_k(f_{i-1}(k),w_{i}(j-k))，其中 wiw_i 均为凸函数，直接操作可能是 O(n∑∣wi∣)O(n\sum|w_i|) 的。但是这是凸包连加，若化为 f[l,r]=f[l,m]∘f[m+1,r]f_{[l,r]}=f_{[l,m]}\circ f_{[m+1,r]}（其中 m=(l+r)/2m=(l+r)/2，∘\circ 是求闵可夫斯基和），分治递归下去即为 O(∑∣wi∣log⁡n)O\Big(\sum |w_i|\log n\Big) 。
这个操作和求一次函数连乘（分治，O(nlog⁡2n)O(n\log^2n)）相似。
记 hih_i 表示在 [i,i+L)[i,i+L) 上做出来一个 MOO 的花费，然后设 f[l,r],x∈[0,2],y∈[0,2](i)f_{[l,r],x\in[0,2],y\in[0,2]}(i) 表示区间 [l,r][l,r] 中，左边空出 xx 个格子，右边空出 yy 个格子，做出至少 ii 个 MOO 的最小花费。转移时枚举 mm 是 MOO 的哪一位（或者根本不在这里放 MOO），闵可夫斯基和后直接取 min⁡\min 即可。复杂度 O(L2nlog⁡n)O(L^2n\log n)，因为对于长度为 lenlen 的区间来说，其上的凸包长度只有 ⌊len/L⌋\lfloor len/L \rfloor。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...