洛谷P3655 差分数组 树状数组

时间：2022-12-19 16:41:28

题目链接：https://www.luogu.org/problemnew/show/P3655

不一定对，仅供参考，不喜勿喷，不喜勿喷。

先copy洛谷P3368 【模板】树状数组 2 题解里面一位大佬Lyp10000对差分数组的解释：

来介绍一下差分

设数组a[]={1,6,8,5,10}，那么差分数组b[]={1,5,2,-3,5}

也就是说b[i]=a[i]-a[i-1];(a[0]=0;)，那么a[i]=b[1]+....+b[i];(这个很好证的)。

假如区间[2,4]都加上2的话

a数组变为a[]={1,8,10,7,10}，b数组变为b={1,7,2,-3,3};

发现了没有，b数组只有b[2]和b[5]变了，因为区间[2,4]是同时加上2的,所以在区间内b[i]-b[i-1]是不变的.

所以对区间[x,y]进行修改,只用修改b[x]与b[y+1]:

b[x]=b[x]+k;b[y+1]=b[y+1]-k;

 

看题目很容易想到差分数组，但是现在不是直接求出差分数组的和，而是要对求出的差分数组的每一个元素判断正负之后，然后再通过题目中给的那个公式进行加工，最后求出加工之后数组的和，在这里我们吧加工之后的数组用树状数组来存，这样容易修改和求和，我们分别用数组a，b，c来代表原始数据，原始数据的差分数组，差分数组对应的树状数组。

因为树状数组的值取决于差分数组的值，根据差分数组的性质，当我们在修改数组a（原始数据）的某个区间，即同时让a数组上区间[L，R]之间的数增加value，事实上在差分数组里面（b数组）只改变了b[L]，和b[R+1]（如果R+1不越界的话），其中b[L]增加了value，b[R+1]减少了value。根据这个性质，我们发现，因为差分数组每次只改变两个值（b[L]，b[R+1]），那么其实对应的树状数组也只需要执行两个单点修改的操作，即add（L，？），add（R+1，？），这里面的两个问号就代表着我们要在树状数组里面单点修改时改变的差值。

那么这个改变的差值是很好求的，只要求出未改变之前的值，和改变之后对应的值，用后者减前者就是改变的差值。也就是这个操作：

LL cal(LL x,LL value){//cal函数是计算当差分数组的b[x]加上value时，对应的树状数组应该更改的值 
    
    LL A,B;//a代表未改变时的值，b表示改变之后的值 
    //b-a就是他们之间的差值，也就是改变的差值 
    if(b[x]>0)
    A=-S*abs(b[x]);
    else
    A=T*abs(b[x]);
    
    if(b[x]+value>0)
    B=-S*abs(b[x]+value);
    else
    B=T*abs(b[x]+value);
    return B-A;
    
    /*if(b[x]>0){
        if(b[x]+value>0)
        return -S*(abs(b[x]+value))-(-S*abs(b[x]));
        else
        return T*(abs(b[x]+value))-(-S*abs(b[x]));
    }else{
        if(b[x]+value<0)
        return T*(abs(b[x]+value))-(T*abs(b[x]));
        else
        return -S*(abs(b[x]+value))-(T*abs(b[x]));
    }*/
}

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque> 
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 200005
LL N,Q,S,T;
LL a[maxn],b[maxn],c[maxn];
LL lowbit(LL x){
    return x&(-x);
}
LL sum(LL x){
    LL ans=0;
    while(x){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
void add(LL x,LL value){
    while(x<maxn){
        c[x]+=value;
        x+=lowbit(x);
    }
}
LL cal(LL x,LL value){//cal函数是计算当差分数组的b[x]加上value时，对应的树状数组应该更改的值 
    
    LL A,B;//a代表未改变时的值，b表示改变之后的值 
    //b-a就是他们之间的差值，也就是改变的差值 
    if(b[x]>0)
    A=-S*abs(b[x]);
    else
    A=T*abs(b[x]);
    
    if(b[x]+value>0)
    B=-S*abs(b[x]+value);
    else
    B=T*abs(b[x]+value);
    return B-A;
    
    /*if(b[x]>0){
        if(b[x]+value>0)
        return -S*(abs(b[x]+value))-(-S*abs(b[x]));
        else
        return T*(abs(b[x]+value))-(-S*abs(b[x]));
    }else{
        if(b[x]+value<0)
        return T*(abs(b[x]+value))-(T*abs(b[x]));
        else
        return -S*(abs(b[x]+value))-(T*abs(b[x]));
    }*/
}
int main()
{
    while(scanf("%lld%lld%lld%lld",&N,&Q,&S,&T)!=EOF){
        memset(c,0,sizeof(c));//树状数组清零 
        scanf("%lld",&a[0]);
        b[0]=0;
        for(int i=1;i<=N;i++){
            scanf("%lld",&a[i]);
            b[i]=a[i]-a[i-1];//b数组是差分数组，即b[i]=a[i]-a[i-1](定义) 
            if(b[i]<0)//先把一开始的差分数组对应的树状数组求出来 
            add(i,T*abs(b[i]));
            else
            add(i,-S*abs(b[i]));
        }
        LL x,y,value;
        while(Q--){
            scanf("%lld%lld%lld",&x,&y,&value);
            add(x,cal(x,value));//cal函数得到c[x]位置处的改变值,然后对树状数组进行单点修改 
            if(y+1<=N){//判断是否越界 
                add(y+1,cal(y+1,-value));//和上面一样 
            }
            b[x]+=value;//前面的b数组不可以改变，在这里改变他的值,因为我们每次都要和前一次值只比较 
            b[y+1]-=value;
            printf("%lld\n",sum(N));//输出差分数组的总和 
        }
    }
    return 0;
}

 

标签：

相关文章