洛谷 P2367 语文成绩 刷题笔记

P2367 语文成绩 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

差分 

令a[i]为b[i]数组的前缀和

a[n]=b[1]+b[2]+b[3]+.....+b[n];

a[n-1]=b[1]+b[2]+b[3]+.....+b[n-1];

构造差分数组 b[i]=a[i]-a[i-1];

有什么好处 当我们想对a[l]--a[r]范围内所有数据加上一个数x

不必循环 for(int i=l;i<=r;i++) a[i]+=x;

直接

b[l]+=c;//从l-n的范围全部+c;

b[r+1]-=c;//将r+1到n范围多加的C减掉

自此我们快速将一个循环才能完成的操作优化 （主要是为了以后学二维的差分做铺垫）

对于构造差分数组 我们采取 add ()函数 

void add(int l,int r,int x){
    b[l]+=x;
    b[r+1]-=x;
    
}

for(int i=1;i<=n;i++){
        cin>>a[i];
        add(i,i,a[i]);//构造b[i] 差分数组
         
    }

该函数 在首次输入a[i]数组构造差分数组的效果

等价于 b[i]=a[i]-a[i-1]

为什么呢

我们传入了两个i

传进add后 

相当于 

b[i]这个数加上了a[i]

而b[i+1]这个数减去了a[i]

///这一部操作是因为  b[i]=a[i]-a[i-1] 在我们输入下一个a[i]时

//当前的这个a[i]就是下一个a[i]的”a[i-1]"而我们要减去的a[i-1]其实在上一次输入时就已经先减去了

所以读入当前a[i] 只要将b[i](它的值是 -a[i-1] )加上这个a[i]即可 

那我为什么不直接写 b[i]=a[i]-a[i-1] 其实完全没问题 

只是二维差分数组的构造 也采取add 这里先讲了add的原理 以便进一步理解二维差分数组的构造

完整代码

#include<iostream>
using namespace std;
const int N=5e6+10;
int a[N],b[N];
void add(int l,int r,int x){
    b[l]+=x;
    b[r+1]-=x;
    
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        add(i,i,a[i]);//构造b[i] 差分数组

//此处的insert 操作的实际效果 
    //与该语句  b[i]=a[i]-a[i-1];  相同 ；
        //初始化 插入差分数组  
        //使b[i]变成当前  a[i]的差分数组 
    //b数组为空 将a数组的原始值插入b数组 就是按照差分处理的形式
    //初始化b数组的原始缓存  
         
    }
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);

                //执行增值操作  
        //但是只是对差分数组  进行了增值操作  
        //a数组是b数组的前缀和数组 
        //而b数组 就是a数组 未经扫描的冗沉 缓存
        //我们对b数组的操作 只是暂时记录了增减情况 还没把这个情况汇报给a数组

    }

    for(int i=1;i<=n;i++){
        a[i]=a[i-1]+b[i];

         //扫描一编操作的增减值 
        //计算前缀和  
      
    }
    
    int minn=a[1];
    for(int i=1;i<=n;i++){
    
        minn=min(a[i],minn);
    }
    cout<<minn;
    return 0;
}

举个例子模拟一下缓存池情况 

对于以下代码

插入改组数据

 /*
   
    6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1*/

#include<iostream>
using namespace std;
const int N=100010;
int a[N],b[N];    int n,m;
void insert(int l,int r,int c){

    b[l]+=c;
    //b[l]到n的位置加上  c 
    b[r+1]-=c;
    //减去 上一步中多加的【r+1】到n的部分
    cout<<"当前缓存池 is  ";
    for(int i=1;i<=n;i++){
        cout<<b[i]<<' ';
    }
    cout<<endl;
    }
int main(){

    cin>>n>>m;

    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    for(int i=1;i<=n;i++){
        insert(i,i,a[i]);
    //此处的insert 操作的实际效果 
    //与该语句  b[i]=a[i]-a[i-1];  相同 ；
        //初始化 插入差分数组  
        //使b[i]变成当前  a[i]的差分数组 
    //b数组为空 将a数组的原始值插入b数组 就是按照差分处理的形式
    //初始化b数组的原始缓存  
    }
    
   
    while(m--){
    
        int l,r,c;
        cin>>l>>r>>c;
        insert (l,r,c);
        //执行增值操作  
        //但是只是对差分数组  进行了增值操作  
        //a数组是b数组的前缀和数组 
        //而b数组 就是a数组 未经扫描的冗沉 缓存
        //我们对b数组的操作 只是暂时记录了增减情况 还没把这个情况汇报给a数组 
         
    }
    for(int i=1;i<=n;i++){
    
        a[i]=a[i-1]+b[i];
        //扫描一编操作的增减值 
        //计算前缀和  
    }
    for(int i=1;i<=n;i++){
    
        //cout<<a[i]<<' ';
    }
    return 0;
}

缓存池情况