前缀和 差分

1.前缀和

原题链接

这里的数据不需要两个数组，开两个就ME了，从左往右，从上往下直接滚动s数组就行

#include<iostream>
#include<cstring>

using namespace std;

const int N=5050;

int s[N][N];

int main()
{
    int N,R;
    cin>>N>>R;
    int n=R,m=R;
    for(int i=0;i<N;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        x++,y++;
        s[x][y]+=w;
        n=max(n,x),m=max(m,y);//至少是R*R初坐标开始枚举
    }
    //求二维前缀和
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
    //求边长为R的正方形的最大值
    int res=0;
    for(int i=R;i<=n;i++)
        for(int j=R;j<=m;j++)
            res=max(res,s[i][j]-s[i-R][j]-s[i][j-R]+s[i-R][j-R]);
    cout<<res<<endl;
    return 0;
}

2.差分

原题链接

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;
const int N=1e5+10;

int a[N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
        
    //先处理成差分数组
    for(int i=n;i>1;i--)
        a[i]-=a[i-1];
    
    LL p=0,q=0;    
    //b2~bn中找正数总和与负数总和
    for(int i=2;i<=n;i++)
    {
        if(a[i]>0)  p+=a[i];
        else if(a[i]<0) q-=a[i];
    }
    cout<<max(p,q)<<endl;
    cout<<abs(p-q)+1<<endl;
    
    return 0;
}

3.差分与前缀和

原题链接

#include<iostream>
#include<map>

using namespace std;
const int N=1e4+10;

map<pair<int,int> ,bool> existed;
int d[N],c[N];

int main()
{
    int n,p,h,m;
    cin>>n>>p>>h>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        if(a>b)swap(a,b);
        if(existed[make_pair(a,b)])continue;
        d[a+1]--,d[b]++;
        existed[make_pair(a,b)]=true;
    }
    for(int i=1;i<=n;i++)
    {
        c[i]=c[i-1]+d[i];
        cout<<c[i]+h<<endl;
    }
}