再谈 前缀和,差分

预计学习时间: 一天

因为发现有好多题目都需要利用前缀和还有差分来进行优化,所以要花一天的时间把这种基础算法学完.

//前缀和:
//二维前缀和:
//1-1 激光炸弹: https://www.luogu.com.cn/problem/P2280
//这里只需要建立一个二维前缀和,然后遍历每一个框架就可以
//不能枚举所有的点,因为点实在是太多了
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5010;
int n,r,s[N][N],res;
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>r;
    r=min(r,5002);
    for(int i=0;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        s[a][b]+=c;
        //因为如果点在边上的话,是无效的,所以我们的框是要框住比自己小的
        //3x3的框就要框2x2的炸弹
    }
    for(int i=1;i<=5002;i++)
        for(int j=1;j<=5002;j++) s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    for(int i=r;i<=5002;i++) 
        for(int j=r;j<=5002;j++) res=max(res,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);
    cout<<res;
    return 0;
}

//差分
//增减序列:https://ac.nowcoder.com/acm/contest/999/B
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long res,ans,c[N],n,a[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],c[i]=a[i]-a[i-1];
    for(int i=2;i<=n;i++){
        if(c[i]>0) res+=c[i];//统计所有的差分正数
        else if(c[i]<0) ans-=c[i];//所有的差分负数
    //这里讲一下思路: 对于整个差分数列,有正值有负值,那么我们的目标是2-n的序列全变为0
    //通过改变某一区间让min(正,负)变为0,剩下的一个让从1开始到n结束来
    //因为如果改变当前的c[i]值的话,可以巧妙地发现,知识改变的当前的值,后面的c仍然不变,所以可以随意放心的改
    }
    cout<<min(res,ans)+abs(res-ans)<<endl<<abs(res-ans)+1;
    return 0;
}