前缀和与差分

前缀和

一维前缀和

给定一维数组a1,a2,a3,a4,a5,…，前缀和能加速该数组中任意一段的求解

前缀和的存储方式为：f[i] = f[i-1]+a[i]，即第i个前缀和数组中的内容为前i个a的总和，因此通常习惯从1开始存储

求取任意一段a数组的总和：假设我们要求解i~j的a数组的总和，我们可以利用前缀和数组进行如下计算：sum = f[j]-f[i-1]

二维前缀和

给定一个二维数组f[i][j]

$\left[ \begin{matrix} a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33}\\ \end{matrix} \right]$

前缀和f[i][j](与之前单个存储方式共用一个矩阵)的意义为，右下角为i,j的左上角为1，1的矩形的数字之和

对于二维矩阵的前缀和求解通常使用动态规划+容斥原理的方式进行计算

// n为行，m为列
for(int i = 1;i<=n;i++)
    for(int j = 1;j<=n;j++)
        f[i][j] += f[i-1][j]+f[i][j-1]-f[i-1][j-1];

对于给定一个右下角顶点（i，j），并给定这个矩形的变成为r，计算该区域的和为：

// 不计算该矩形边上的点的计算方式，即计算一个r-1的矩形面积
sum = f[i][j] - f[i-r][j]-f[i][j-r]+f[i-r][j-r];
// 计算该矩形边上的点的计算方式，即计算一个r的矩形面积
sum = f[i][j] - f[i-r-1][j]-f[i][j-r-1]+f[i-r-1][j-r-1];

激光炸弹

解题思路

使用二维前缀和，遍历，每个符合情况的矩形，从中找出一个和最大的结果。

ac代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int f[N][N];
int main(){
    int n,r;
    cin>>n>>r;
    // 存在所要求的矩形面积比地图大
    int c = r,k=r;
    // 先对地图进行存储
    for(int i = 0,x,y,w;i<n;i++){
        cin>>x>>y>>w;
        x++,y++;
        // 获取地图边界
        c = max(x,c),k = max(y,k);
        f[x][y]+=w;
    }
    // 计算前缀和
    for(int i = 1;i<=c;i++)
        for(int j = 1;j<=k;j++)
            f[i][j] += f[i-1][j]+f[i][j-1]-f[i-1][j-1];
    // 遍历所有符合情况的矩形框，并找出求和值最大的结果
    int res = 0;
    for(int i = r;i<=c;i++)
        for(int j = r;j<=k;j++)
            res = max(res,f[i][j] - f[i-r][j]-f[i][j-r]+f[i-r][j-r]);
    cout<<res<<endl;
    return 0;
}

差分

差分序列的定义

给定一个正常序列a： $a_1,a_2,a_3,.....,a_n$

那么这个序列的差分序列b： $b_1,b_2,b_3,....., b_n$

对于i>0，b[i]的定义为：

$b[i] = \begin{cases} a[i]-a[i-1],i \neq 1\\ a[i],i=1 \end{cases}$

两个结论

a是b的前缀和序列

举个栗子

现有正常序列a： $1,2,3,4$

其差分序列为b： $1,1,1,1$

看看a[4] = b[4]+b[3]+b[2]+b[1] = 1+1+1+1 = 4

结论无误

对a中的在区间[l,r]上的数字加上x，等价与在其差分序列b上进行，b[l]+=x,b[r+1]-=x

还是用上面的栗子

假设我们现在对[2,3]的序列加上x=3：

正确的结果应该为a： $1,5,6,4$

按照上面的方式进行b： $1,4,1,-2$

b映射出的a： $1,5,6,4$

结果与目标一致。

使用正经的解释：

从[l,r]上加x，那么区间内元素的差距其实是没有变的，需要修改的是第一个的值和最后一个的值，因为从l开始，因此需要给l加上一个x，到r结束，r+x的结果不变，但是后面就不能再加了，因此在r+1的地方需要减去一个x

增减序列

解题思路

通过差分的定义，我们可以明白，差分的序列的意思是当前数字与上一个数字的之间的差距。题目要求所有的数字都相同，那么说明，我们的差分序列在区间[2,n]的值全部为0，说明其中没有差异，为什么不用管第一个呢，因为第一个表示的是初值，其他全部为0说明其他的地方永远和第一个的值相同。

我们知道使用在 $[l,r]$ 区间上做加减是需要做一个加法一个减法的。

我们可以选择差分数组中任意两个索引，如果差分值为负数，我们就做加法，为正数就做减法，这应该是能够最快使得我们的差分序列全部变成0的最快方法。

数组中可以供选择的方式如下：

2<=i,j<=n：这种情况下可以修改两个值，应该尽可能多地使用这种方式
i =1,2<=j<=n：这种情况下说明只有正或负，选择修改第一个的数值，这种时候只能修改1个数趋近与0
2<=i<=n，j=n+1：这种情况说明只有正或负，选择修改最后一个的值，这种时候也只能修改1个数字趋近与0

对于上面选择的3种方式，应该尽可能多地使用第1种，然后在只有单一情况下才选择2，3种

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long ll;
// 这个是差分数组
ll a[N];
int main(){
    int n;
    cin>>n;
    ll pos=0,neg=0;
    // 先存储数据
    for(int i =1;i<=n;i++)cin>>a[i];
    // 再把数据转化为差分数组
    for(int i = n;i>1;i--)a[i]-=a[i-1];
    // 使用贪心策略，先选择一正一负的进行操作，然后在处理正(与第一位进行计算)或处理负的(与最后一位进行处理)
    // 分别记录正数和负数的数量
    for(int i = 2;i<=n;i++){
        if(a[i]>0)pos+=a[i];
        else neg-=a[i];
    }
    // 操作的最少次数：max(正，负)  就是要把负数或者正数中的最大那个变成0，因为小的那个会在大的变化过程中变成0，然后执行单边操作
    // 操作的可能性：abs(正-负)+1   就是只做单边的情况，即只对正数或只对负数处理的可能性，减法过程中会漏掉一种情况因此需要+一个1
    cout<<max(neg,pos)<<endl;
    cout<<abs(neg-pos)+1<<endl;
    return 0;
}

最高的牛

解题思路

这个是不是可以用差分写啊，对吧，对吧！

怎么说呢，我们先假设所有的牛都是最高的，然后现在输入了一组能够相互看到的牛，那我们直接把在他们之间的牛最高身高减个一不就行了嘛？

比如输入a,b，那么从a+1到b-1的位置减1，换成代码就是f[a+1]–,f[b-1+1]++

不过好像有重复输入的原因，所以需要用个set确认这个输入之前出现过嘛就i可以了

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
// 差分数组
int height[N];
int n,p,h,m;
int main(){
    cin>>n>>p>>h>>m;
    // 初始化差分数组，使得原数组的值全部为h
    height[1] = h;
    // 去重
    set<pair<int,int>> exsits;
    while(m--){
        int a,b;
        cin>>a>>b;
        // 一定要小的在前面，不然你差分就计算错了
        if(a>b)swap(a,b);
        if(!exsits.count({a,b})){
            exsits.insert({a,b});
            // a+1到b-1的位置都-1
            height[a+1]--,height[b]++;
        }
    }
    // 将差分数组转化成正常数组
    for(int i = 1;i<=n;i++){
        height[i] += height[i-1];
        cout<<height[i]<<endl;
    }
    return 0;
}