用于处理在一个数组的连续区间上进行等差序列的增减

例如:给1-5这个区间增加12345

多次操作后,问数组的最终值

方法就是二阶差分,推导一下就行

1
2
3
4
5
6
7
              变化值
               下标
数组 	0 1 2 3 4 5   6 7 8 9 10
初始     0 0 0 0 0 0   0 0 0 0 0
变化     0 1 3 5 7 9   0 0 0 0 0
一阶     0 1 2 2 2 2  -9 0 0 0 0
二阶     0 1 1 0 0 0 -11 9 0 0 0

所以规律:

1
2
3
4
5
ll d=(e-s)/(r-l);//s第一个位置的值,e最后一个位置的值,r,l是区间范围
b[l]=b[l]+s;
b[l+1]=b[l+1]+d-s;
b[r+1]=b[r+1]-(d+e);
b[r+2]=b[r+2]+e;

然后难一点的话就是阶梯型的修改如123454321这种,然后再不保证l,r一定在范围内,自己推导就行

1
2
3
4
5
6
7
8
9
10
11
12
vector<ll> d(n+5,0);
for(int i=1;i<=mid;i++){
  ll p=keng[i].fs,f=keng[i].sd;
  d[p+1]-=2;
  if(p+f+1<=n) d[p+f+1]+=1;
  if(p-f+1>=0) d[p-f+1]+=1;
  else{
    ll s=f-p+1;
    d[1]+=s;
    d[2]+=1-s;
  }
}