hqzx_610fuziyu @ 2024-10-08 17:38:58

#include<bits/stdc++.h>
using namespace std;
int a[500005],m,n,xiao;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        if(x>y)swap(x,y);
        a[x]+=z;
        a[y+1]-=z;
    }
    for(int i=1;i<=n;i++)
    {
        a[i]+=a[i-1];   
    }
    for(int i=1;i<=n;i++)
    {
        xiao=min(a[i],xiao);
    }
    cout<<xiao;
    return 0;
}

by badn @ 2024-10-08 18:16:25

没有差分预处理: a[i]=a[i]-a[i-1]

by hqzx_610fuziyu @ 2024-10-27 21:28:50

@badn 大神，具体怎么改啊？（请问差分要预处理吗？）

by badn @ 2024-10-28 18:34:09

代码修改如下。

#include<bits/stdc++.h>
using namespace std;
int a[5000005],d[5000005],m,n,xiao=INT_MAX;//错误1：xiao初始为正无穷，用来存数组中的最小值 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        d[i]=a[i]-a[i-1];//错误二：没有差分预处理 
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        if(x>y)swap(x,y);
        d[x]+=z;
        d[y+1]-=z;
    }
    for(int i=1;i<=n;i++)
    {
        a[i]=a[i-1]+d[i];   
    }
    for(int i=1;i<=n;i++)
    {
        xiao=min(a[i],xiao);
    }
    cout<<xiao;
    return 0;
}

差分的话，用d[i]=a[i]=a[i-1]来保存a数组的每一位与前面的差，相当于a数组每一位的变化趋势。

例如a={1,2,4,6,7,8,10,100},d就等于{1,1,2,2,1,1,2,90}，对d修改，做前缀和就得到a的实际情况。

若是让3~7这一段加一,相当于d[3]+=1,d[7+1]-=1,得d={1,1,3,2,1,1,2,89},做前缀和得a={1,2,5,7,9,11,100}，发现刚好符合。

d[3]+1后，做前缀和会使3~8这一段都加1，再让d[8]-1后会使8~8这一段也就是第八位减一，最终结果就相当于3~7这一段加一。

若进行n次操作，每次就只要对d数组中的两位进行操作最后再做前缀和得到a，复杂度O(2n+n)即O(n)，而要是每次暴力修改的话n次操作，复杂度是O(n^2)，前提是对a数组提前进行一次前缀和的逆运算-差分。

本蒟蒻解释的不算很清，你如果你还有不懂可以查阅网上资料或问问老师