广义差分

前言

对于许多区间操作的题目,差分是普遍且好用的技巧,在此做个归纳整理

例题1

luogu 3943

题意

给定1个长度为\(n\)的01数组,其中1的个数为\(k\)

你可以进行\(m\)种操作,第\(i\)种操作的长度为\(l_i\),表示可以将长度为\(l_i\)的区间异或1。

询问最少需要多少次操作,使得整个数组变成0。

\(1 \leq k \leq 8 , 1 \leq n \leq 4 \times10 ^4 , 1 \leq m \leq 64\)

题解

直接做的话是没法做的,对整个区间异或,各区间相互交叉影响复杂,无从入手。

考虑转化问题,将区间异或转化成对区间端点的异或。即广为人知的差分思想,便于简化问题。

具体地,可以结合异或的性质进行处理。假设我们求出原数组的差分数组(即\(d[i] = a[i] xor a[i - 1]\));那么我们对原数组的区间\([l,r]\)进行异或可以等价于\(d[l] = d[l] xor 1 , d[r + 1] = d[r + 1] xor 1\),目标结果\(a[1 \rightarrow n] = 0\)可以等价于\(d[1 \rightarrow n + 1] = 0\)

由此,问题得以转化:在1个01数组上有不超过\(2k \leq 16\)个1。每次操作可以选择其中的两个位置\(x,y\),令\(d[x] = d[x] xor 1 , d[y] = d[y] xor 1\),前提是\(y - x \in L\)。询问最少操作次数,令\(d[i]\)全部为0。

1的个数很少,因而不难想到1个状压dp的框架,设\(f[s]\)表示将\(s\)集合的1全部变成0的最小操作次数,转移时先找到第1个1,枚举哪1个1跟它匹配,相应转移。复杂度\(O(s \times 2k)\)

问题转化为如何计算任意2个1都变为0的最小代价。

有一种看起来相当有理有据的做法。不妨从\(y - x \in L\)进行迁移,若\(y - x = l_1 + l_2\),同样可以相消,依据是1个位置异或2次不变,故可以实现区间的拼接;类推下去,我们可以将\(L\)集合看作若干物品,有\(l_i\)和$-l_i \(两种价值,求解填充\)y - x$的最少物品数目。但存在某些严重的问题(感谢Epworth),我们做完全背包时,对于正价值和负价值的物品是要分开处理的,这样一来我们没法确定价值上限;另外,即使价值上限开得足够大也是错的,因为我们实际的翻转,左端点不能小于1,右端点不能大于n + 1,而基于相对位置的方案则没有考虑这一点,没法根据绝对位置进行调整。因而是错误的。

假若两个1之间可以使用1次规则,则最小代价为1;否则这2个1需要若干个规则联合消去。具体地,若1个规则应用于1个0和1个1上,则相当于将1传到了0的位置上,则问题转化为该1新的位置与另1个1匹配。可以发现该问题具有传递性,可以构图处理。具体地,我们从各个位置出发,根据已有的规则将其与可匹配位置连边;则两个位置间的最小代价即为这两个位置在图上的最短路径长度,由于边权全部为1,可用BFS处理,时间复杂度\(O(2knm)\)

代码见此

相关练习

luogu 4552

题意

给定1个长度为\(n\)的序列,你每次可以选定1个任意长度的区间,使得整个区间加1或减1。

询问最少的操作次数,使得整个区间全部相同。并询问在操作次数最少的前提下,最终数列的数的种类数。

\(1 \leq n \leq 10^5\)

题解

首先求出原数组的差分数组\(diff[i] = a[i] - a[i - 1]\);区间加可转换为\(diff[l] ++,diff[r + 1] --\),区间减可转化为\(diff[l] -- , diff[r + 1] ++\)。当\(r = n\)时,仅\(diff[l] --\)有效。

最终目的是\(diff[1] = a[1] ,\forall i \in[2,n] ,diff[i] = 0\),求最小操作次数。

考虑每次操作的影响:\(l = 1\)时没有意义;\(l \neq 1 且 r \neq n\)时可以改变2个\(diff\)\(l \neq 1且l = n\)可以改变1个\(diff\)

各个元素是独立的,当\(diff\)变为0时就没有操作的必要。故优先考虑双向成全的操作,即对1个正数和1个负数进行操作;最终只剩下正数或只剩下负数时,再用\(l \neq 1且l = n\)进行处理,即可知最小操作次数。公式可以\(O(n)\)求,即$diff[2 \rightarrow n] \(中,正数的之和\)up\(与负数之和\)dow$的绝对值的最大值。

考虑改动\(diff[1]\)的情况,\(diff[1]\)每变化1,至多能使$diff[2 \rightarrow n] \(的操作次数减1,总操作次数不变。具体地,设\)lim = abs(up + dow)$ ,若\(diff[1]\)的变化量小于等于\(lim\),则总操作次数不变;否则总操作次数一定变大。

最优解的方案数为\(lim + 1\)。时间复杂度\(O(n)\)代码见此

相关文章
相关标签/搜索