Home 前缀和&差分
Post
Cancel

前缀和&差分

前缀和

来一道二维前缀和的模板题 (简单但有点坑):

AcWing 99 激光炸弹

Link

坑点 1: 不同目标可能在同一位置, 也就是说可能两次输入的是同一坐标点处的权值, 所以要 w[i][j]+=a;

坑点 2: 输入的 x,y 的范围是从 0 开始的, 而我们二维前缀和的矩阵是从 1 开始的, 所以要 w[++x][++y];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
const int N=5010;
int n,r,x,y,a,ans;
int w[N+10][N+10];
int main() {
    scanf("%d%d",&n,&r);
    r=min(r,N);
    for(int i=1;i<=n;++i){
        scanf("%d%d%d",&x,&y,&a);
        w[++x][++y]+=a;
    }
    for(int i=1;i<=N;++i)
        for(int j=1;j<=N;++j)
            w[i][j]+=w[i-1][j]+w[i][j-1]-w[i-1][j-1];
    for(int i=r;i<=N;++i)
        for(int j=r;j<=N;++j)
            ans=max(ans,w[i][j]-w[i-r][j]-w[i][j-r]+w[i-r][j-r]);
    printf("%d\n",ans);
    return 0;
}

差分

模板

差分板子 (实际上是 忘记这是哪道题的代码了):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
int n,p,x,y,z,ans=0x3f3f3f3f;
int a[5000010];
int main() {
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=n;i>=1;--i)
        a[i]-=a[i-1];
    while(p--){
        scanf("%d%d%d",&x,&y,&z);
        a[x]+=z;
        a[y+1]-=z;
    }
    for(int i=1;i<=n;++i){
        a[i]+=a[i-1];
        ans=min(ans,a[i]);
    }
    printf("%d\n",ans);
    return 0;
}

AcWing 100 增减序列

Link

这题想清楚了就会豁然开朗.

都知道是差分+贪心. 具体应该这么去想: 对于相邻的两个数 a[i]a[i-1], 如果 a[i] 大于 a[i-1], 那么想要 a[i] 等于 a[i-1] 就只能增大 a[i-1]、减小 a[i], 而 a[i] 的增加量的绝对值加上 a[i-1] 的减少量的绝对值就是 a[i]a[i-1] 的差值的绝对值. 另一种情况同理.

我们的目的是要将整个序列变成相等的, 那么就是要让差分数组全部变为 0. 假设原数组的差分数组是 p, 如果 p[i]>0, 那么它肯定是要被减去 p[i] 的, 至于怎么减去的我们现在无法确定; 如果 p[i]<0, 那么它肯定是要被加上 -p[i] 的. 再联系一下差分数组和原数组区间和对关系, 容易想到正负配对来确定一个操作区间, 这样可以让原本要进行两次以上的操作合为一次.

举个🌰, 我们假设差分数组中恰好出现了 p[i]=-3,p[j]=4, 那么很容易想到可以对区间 [i,j-1] 进行加 3 操作, 于是 p[i]=0,p[j]=1. 如果不这么做, 那就要先对区间 [i,i+1] 进行加 3 操作, 再对 [j,j+1] 进行减 4 操作, 这样虽然让 p[i]p[j] 为 0 了, 但是 ij 之间的数彼此之间的差分却还不一定为 0.

利用贪心的思想很容易论证正负配对的最优性. 那么问题来了, 刚才虽然配对了 -3 和 4, 但是 4 还残留了 1 怎么办? 很简单, 再去看看有没有 -1 或者其他负数可以配对. 如果没有, 就只能对 p[j] 所代表的区间进行其他处理了.

也就是说, 配对结束后, 剩下的全都是像 p[j] 这样的残留物, 并且最后差分就只剩同符号的数 (如果有异号就说明还可以继续配对), 即所有的 p[j] 全都同号.

正负配对抵消的操作共有 min(pos,neg) 次, 假设正数比较多, 那么负数配对完之后剩下的就全都是正数. 这里的 posp 中正数的个数, neg 是负数的个数.

最终结果可能依然不是全 0 的, 因为 abs(sum(正数)) 可能不等于 abs(sum(负数)).

最后不等于 0 的数 (即剩下的同符号的数) 只能通过 p[1]p[n+1] 这两个对差分数组没有影响的差分来一个一个地把自己减为 0 (p[1]a[1]a[0] 的差分, p[n+1]a[n+1]a[n] 的差分, 而数组范围是 [1,n]. 例如通过 p[1]p[j]=1 变成 p[j]=0 的步骤是: p[1]+=1,p[j]-=1. 意思是把原数组区间 [1,j-1] 中的数全都加 1, 其他的数保持不变).

对所有 j 属于 [2,n]p 值不为 0 的 p[j] 而言, 通过 p[1] 把自己变成 0 后, 差分数组 p 就已经全部为 0, 原数组的所有元素也就全部相等了.

这一步的操作共有 abs(pos-neg) 次, 按照刚才正数比较多的假设, 这就是把剩下的没有匹配到负数的正数全都处理完.

因此 ans1=min(pos,neg)+abs(pos−neg)=max(pos,neg).

实际上, 仔细想想就会发现, 如果我们当初对所有剩下的没有被匹配的 p[j]只用 p[1]只用 p[n+1] 来处理, 那么最后原数组全部相等时的元素值其实就是 p[1] (因为 p[1]=a[1]−a[0]=a[1]) 或 -p[n+1] (因为 p[n+1]=a[n+1]−a[n]=-a[n]).

注意题目中所说的“在保证最少次数的前提下, 最终得到的数列可能有多少种”的意思是, 最后全部相等的数组元素可以不止一种. 这很显然啊, 因为我们当初既可以对所有剩下的没有被匹配的 p[j] 都用 p[1] 来处理, 也可以都用 p[n+1] 来处理, 甚至可以一部分用 p[1]、一部分 p[n+1] 来处理, 这样就可以得到多种结果. 也就是说, 我们对 p[1]p[n+1] 的操作次数之和就是剩下的没有被匹配的 p[j] 的个数.

之前正负匹配的时候, 我们只是对负数和正数对进行操作, 所以 p[1]p[n+1] 都没有变, 变的是 p[2]~p[n]. 然后差分数组就只剩下同符号的数, 此时有两种方案:

  1. p[1]+=1,p[j]-=1;
  2. p[j]-=1,p[n+1]+=1.

只用 p[1] 或只用 p[n+1] 处理, 都只有一种结果, 因此现在有了 2 种不同结果; 而操作次数一共是 abs(pos-neg), 因此可以分为:

  • 用 1 次 p[1], 用 abs(pos-neg)−1p[n+1];
  • 用 2 次 p[1], 用 abs(pos-neg)−2p[n+1];
  • abs(pos-neg)−1p[1], 用 1 次 p[n+1].

上面就又分出了 abs(pos-neg)-1 种方案.

所以 ans2=abs(pos-neg)-1+2=abs(pos-neg)+1.

现在懂了吧. AC 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
typedef long long ll;
int n;
ll a[100010],x,y,ans1,ans2;
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i]);
    for(int i=2;i<=n;++i){
        ll p=a[i]-a[i-1];
        if(p>0) x+=p;
        else y-=p;
    }
    ans1=max(x,y),ans2=abs(x-y)+1;
    printf("%lld\n%lld\n",ans1,ans2);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.