题解报告(差分模板)

      差分算法:

     给定n长度的数组,有m个请求,每个请求都是在 [l,r](l<=n;r<=n)区间内加上数c,最后输出该数组。

    若用暴力法求解,需要循环m个请求,每个请求都是需要遍历数组 (r-l) 遍 ((r-l)<=n)。其中的时间复杂度为O(mn)(数据范围在10e3左右)。而运用差分算法,可以将时间复杂度降到线性即O(m+n);(数据范围可以在10e7左右)

     接下来具体讲解差分算法

     题解报告(差分模板)

 

     由此可以看出差分实际上是前缀和运算的逆运算。当需要做出在 [l,r] 区间内的元素加上c的操作时,需要做出的操作为 b[ l ]+=c,由于a数组为b数组的前缀和,所以a数组在 l 后的元素都会自动加上c。而由于是在闭区间内,大于 r 下标

的元素需要减去相应的c,来抵消前面相加的c。此时的操作为 b[ r+1] -=c; 而这一步操作的时间复杂度为O(m);

  在计算好差分数组后,(在初始化b数组时,值为0)   如何得到操作后的数组a,可以有两个思路:

  个人:对于b数组计算b数组中的每一个前缀和,即遍历b数组,b[i]+=b[i-1];这样子相当于得到了对于每一个下标的操作c的具体值,a数组想要得到操作后的数组,只需要和计算前缀和后的b数组对于的下标相加即可

  y总:可以将a数组中的元素可以看成 [l,l] 区间内加入元素 a [ l ] 到b数组中去,先做一遍初始化。然后再做m个请求操作。最后计算b数组的每一个前缀和即可。

  不管哪种方法,实现的时间复杂度为O(n),即数组的长度,最终的时间复杂度为O(n+m),为线性

  注:当 l 和 r 的数值过大,并且差分后的大多数元素并没有遍历到的时候,需要用到离散化的方法。

 

  题目:

  Acwing 797.差分(模板题)

题解报告(差分模板)

 

 

//个人方法
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN=1e6;
int a[MAXN];
int b[MAXN];
int main()
{
    int n,m;
    cin>>n>>m;
    memset(b,0,sizeof(b));//初始化差分数组
    for(int i=1;i<=n;i++) cin>>a[i];//读入原数组
    for(int i=0;i<m;i++)
    {
        int ai,bi,c;
        cin>>ai>>bi>>c;
        b[ai]+=c;
        b[bi+1]-=c;
    }
    for(int i=1;i<=n;i++) b[i]+=b[i-1];//计算差分数组的前缀和,使得差分数组中的对应下标的值为相应的操作后的总值
    for(int i=1;i<=n;i++) a[i]+=b[i];//对于a数组的每一个下标读入相应的操作
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    return 0;
}

 

//y总
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN=1e6;
int a[MAXN];
int b[MAXN];

void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
    return ;
}

int main()
{
    int n,m;
    cin>>n>>m;
    memset(b,0,sizeof(b));//初始化差分数组
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];//读入原数组
        insert(i,i,a[i]);//将原数组视为在区间[i,i]中加上元素a[i]
    }
    for(int i=0;i<m;i++)
    {
        int ai,bi,c;
        cin>>ai>>bi>>c;
        insert(ai,bi,c);
    }
    for(int i=1;i<=n;i++) b[i]+=b[i-1];//计算差分数组的前缀和,使得差分数组中的对应下标的值为相应的操作后的总值
for(int i=1;i<=n;i++) cout<<b[i]<<" "; return 0; }

 

Acwing 2041.干草堆

题解报告(差分模板)

 

该题其实也是模板题,只不过题中的原数组的全部元素默认为0,只需要得到差分数组的各个前缀和即可,由于需要从小到大排序,并且输出中间值,在操作后还需要排序。并且输出最中间的值即下标为(n/2+1)

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=1e6+5;
int st[MAXN],d[MAXN];
int main()
{
  int n,k;
  cin>>n>>k;
  //memset(st,0,sizeof(st));
  memset(d,0,sizeof(d));
  for(int i=1;i<=k;i++)
  {
    int l,r;
    cin>>l>>r;
    d[l]++; d[r+1]--;//对于区间添加干草堆
  }
  for(int i=1;i<=n;i++) d[i]+=d[i-1];//计算前缀和
  sort(d+1,d+n+1);
  cout<<d[n/2+1];//计算中间数
}

 

 

题解报告(差分模板)

 

上一篇:Photoshop打造精致的透明玻璃按钮


下一篇:P8108 [Cnoi2021]绀珠传说 解题报告