浅谈ACM中前缀和的应用

1 牛客小白月赛5 https://www.nowcoder.com/acm/contest/135/I

   Apojacsleam喜欢数组。

    他现在有一个n个元素的数组a，而他要对a[L]-a[R]进行M次操作：

        操作一：将a[L]-a[R]内的元素都加上P

        操作二：将a[L]-a[R]内的元素都减去P

    最后询问a[l]-a[r]内的元素之和？
    请认真看题干及输入描述。
输入描述:
输入共M+3行：

第一行两个数，n，M，意义如“题目描述”

第二行n个数，描述数组。

第3-M+2行，共M行，每行四个数，q，L，R，P，若q为1则表示执行操作2，否则为执行操作1

第4行，两个正整数l，r
输出描述:
一个正整数，为a[l]-a[r]内的元素之和

code：

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
long long a[1000005];
long long s[1000005];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    int op,p,l,r;
    while(m--)
    {
        scanf("%d%d%d%d",&op,&l,&r,&p);
        if(op==1)
        {
            s[r+1]+=p;
            s[l]-=p;
        }
        else
        {
            s[r+1]-=p;
            s[l]+=p;
        }
    }
    cin>>l>>r;
    for(int i=1;i<=n;i++)
    {
        s[i]+=s[i-1];
        a[i]+=(s[i]+a[i-1]);
    }
    cout<<a[r]-a[l-1]<<endl;
    return 0;
}

牛客网暑期ACM多校训练营（第二场）链接
题意：一个n×m的农田，每个小格子都有一种作物，现在喷t次农药，每次农药覆盖一个矩形，该矩形里面与农药类型不同的植物都会死掉，求最后植物的死亡数是多少。

样例输入：

2 2 2
1 2
2 3
1 1 2 2 2
2 1 2 1 1

样例输出：3

正解：
作者：xseventh
链接：https://www.nowcoder.com/discuss/87630?type=101&order=0&pos=14&page=0
来源：牛客网
我们通过差分(其实就是二维前缀和)可以在O(nm)的时间求出每个点被撒了几次肥料
然后我们可以对每种植物分开求被撒了几次相同种类的肥料，然后判断被撒肥料的次数是否等于被撒的相同种类肥料的次数来确定这个植物的死活.

下图是用正解跑出样例的结果。

另一种解法：

通过二维前缀和+随机化算法进行差分，其中还可以通过利用树状数组来代替二维的前缀和

code:
稳过的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
long long  n,m,t;
long long x;
const int N = 1e6+10;
//long long Rand[N];
//vector<long long>mp[N],sum[N];
long long  id(int x,int y)
{
    return (x-1)*(m)+y;
}
int main()
{
    srand(2333);
    scanf("%lld%lld%lld",&n,&m,&t);
    vector<ll> Rand(n*m+1);
    vector<vector<ll>> mp(n+2,vector<ll>(m+2));
    vector<vector<ll>> sum(n+2,vector<ll>(m+2));
    for(long long  i=1; i<=n*m; i++)
    {
        Rand[i] = (1LL*rand()<<15)+rand();
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            scanf("%lld",&x);
            mp[i][j] = x;

        }
    }
    while(t--)
    {
        long long x1,x2,y1,y2,k;
        scanf("%lld%lld%lld%lld%lld",&x1,&y1,&x2,&y2,&k);
        sum[x1][y1]+=Rand[k];
        sum[x2+1][y2+1]+=Rand[k];
        sum[x1][y2+1]-=Rand[k];
        sum[x2+1][y1]-=Rand[k];

    }
    long long  ans  = 0;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            sum[i][j]+=(sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]);
            if(sum[i][j]%Rand[mp[i][j]]!=0)ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

不太稳的做法

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,m,i,j,T,X1,X2,Y1,Y2,k,x;
vector<int> mp[N],sum[N];
int ran[N],die;
signed main()
{
    srand(233);
    scanf("%lld%lld%lld",&n,&m,&T);
    for(i=0;i<=n+1;i++)for(j=0;j<=m+1;j++)sum[i].push_back(0),mp[i].push_back(0);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        scanf("%lld",&x),mp[i][j]=x,ran[(i-1)*m+j]=(rand()<<16)+rand();
    }
    for(i=1;i<=T;i++)
    {
        scanf("%lld%lld%lld%lld%lld",&X1,&Y1,&X2,&Y2,&k);
        sum[X1][Y1]+=ran[k];
        sum[X2+1][Y1]-=ran[k];
        sum[X1][Y2+1]-=ran[k];
        sum[X2+1][Y2+1]+=ran[k];
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
            if(sum[i][j]%ran[mp[i][j]])die++;
        }
    }
    printf("%lld",die);
    return 0;
}

小技巧：int 用 signed 替换
树状数组区间更新做法：https://www.nowcoder.com/discuss/87630?type=101
树状数组前缀和做法 https://blog.csdn.net/weixin_41156591/article/details/81150890
随机化：https://www.nowcoder.com/discuss/87562?type=101&order=0&pos=15&page=0