今天学了 差分********* 很明白 然后 配合着luogu上的题写一下吧 裸的差分 当时一直打暴力60分 交了十几次 今天才知道 查询修改什么的是差分
直接看题把
输入输出格式输入格式：第一行有两个整数n，p，代表学生数与增加分数的次数。第二行有n个数，a1~an，代表各个学生的初始成绩。接下来p行，每行有三个数，x，y，z，代表给第x个到第y个学生每人增加z分。输出格式：输出仅一行，代表更改分数后，全班的最低分。
根据zhw老师说的 先定义一个b数组 用来 加速
就像 b[i]=a[i]-a[i-1]
搞到最后 就等价于
a[i]=b[i]+.......b[1]
操作的话 只需要在b[x]+z b[y+1]-z 就好 加速嘛
代码：
#include<iostream>#include<cstdio>using namespace std;int n,p,x,y,z,a[5000010],b[5000010],ans,sum=1111111;int main(){scanf("%d%d",&n,&p);for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i]-a[i-1]; }for(int i=1;i<=p;i++){scanf("%d%d%d",&x,&y,&z);b[x]+=z;b[y+1]-=z;}for(int i=1;i<=n;i++){ans+=b[i];sum=min(sum,ans);}printf("%d",sum);}
转载于:https://www.cnblogs.com/_Yrh/p/9312907.html
