自动搬运

查看原文

来自洛谷，原作者为

	AC_Automation **

搬运于2025-08-24 21:25:05，当前版本为作者最后更新于2019-03-09 12:57:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

刚调完这道题，感觉坑还是比较多的，于是写一篇题解。

正解：线段树+差分

不会的可以去看看线段树和差分

区间加上一个等差数列可以用差分来解决。

比如：

原序列：0 0 0 0 0 0
差分序列：0 0 0 0 0 0
等差序列：1 3 5 7 9
加上等差数列后的序列：1 3 5 7 9 0
然后差分：1 2 2 2 2 -9

我们称差分序列为$a$，首项为$s$，末项为$e$，公差为$d$，要将$l$~$r$这段区间加上等差序列

可以得出结论：

如果要在差分序列上加一个等差序列，则要在$a_{l}$加上$s$，$a_{l+1}$~$a_r$加上$d$，$a_{r+1}$剪去e即可！

用线段树维护即可，答案即为$\sum _{i=1}^na[i]$

于是就有了代码：

#include<iostream>
using namespace std;
#define ll long long
ll data[100005];
struct point{
    ll sum;
    ll tag;
} a[400005];
inline int ls(int root){return root<<1;}
inline int rs(int root){return root<<1|1;}
inline void up(int root){a[root].sum=a[ls(root)].sum+a[rs(root)].sum;}
void build(int root,int l,int r){
    a[root].tag=0;int mid=(l+r)>>1;
    if(l==r){a[root].sum=data[l];return;}
    build(ls(root),l,mid);build(rs(root),mid+1,r);
    up(root);
}
inline void pd(int root,int l,int r){
    int mid=(l+r)>>1;
    a[ls(root)].tag+=a[root].tag;
    a[rs(root)].tag+=a[root].tag;
    a[ls(root)].sum+=a[root].tag*(mid-l+1);
    a[rs(root)].sum+=a[root].tag*(r-mid);
    a[root].tag=0;
}
void add(int root,int l,int r,int ql,int qr,ll x){
    if(ql<=l&&qr>=r){a[root].tag+=x;a[root].sum+=(r-l+1)*x;return;}
    int mid=(l+r)>>1;
    pd(root,l,r);
    if(ql<=mid)add(ls(root),l,mid,ql,qr,x);
    if(qr>mid) add(rs(root),mid+1,r,ql,qr,x);
    up(root);
    return;
}
ll query(int root,int l,int r,int ql,int qr){
    if(ql<=l&&qr>=r)
        return a[root].sum;
    int mid=(l+r)>>1,ret=0;
    pd(root,l,r);
    if(ql<=mid)ret+=query(ls(root),l,mid,ql,qr);
    if(qr>mid)ret+=query(rs(root),mid+1,r,ql,qr);
    return ret;
}//↑上面全是线段树
int main()
{
    int n,m,opt,l,r,k,d,t;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>data[i];
    for(int i=n-1;i>0;i--)
        data[i+1]=data[i+1]-data[i];//将原序列差分
    build(1,1,n);
    for(int i=0;i<m;i++){
        cin>>opt;
        if(opt==1){
            cin>>l>>r>>k>>d;
            add(1,1,n,l,l,k);
            add(1,1,n,l+1,r,d);
            add(1,1,n,r+1,r+1,-(k+d*(r-l)));//加上等差数列
        }
        else{
            cin>>t;
            cout<<query(1,1,n,1,t)<<endl;
        }
        
    }
    return 0;
}

交上去一看，$80pts$，WA点1，点3

错误在于$r+1$可能会越界，$l+1$可能会$>r$

于是100pts代码：

#include<iostream>
using namespace std;
#define ll long long
ll data[100005];
struct point{
    ll sum;
    ll tag;
} a[400005];
inline int ls(int root){return root<<1;}
inline int rs(int root){return root<<1|1;}
inline void up(int root){a[root].sum=a[ls(root)].sum+a[rs(root)].sum;}
void build(int root,int l,int r){
    a[root].tag=0;int mid=(l+r)>>1;
    if(l==r){a[root].sum=data[l];return;}
    build(ls(root),l,mid);build(rs(root),mid+1,r);
    up(root);
}
inline void pd(int root,int l,int r){
    int mid=(l+r)>>1;
    a[ls(root)].tag+=a[root].tag;
    a[rs(root)].tag+=a[root].tag;
    a[ls(root)].sum+=a[root].tag*(mid-l+1);
    a[rs(root)].sum+=a[root].tag*(r-mid);
    a[root].tag=0;
}
void add(int root,int l,int r,int ql,int qr,ll x){
    if(ql<=l&&qr>=r){a[root].tag+=x;a[root].sum+=(r-l+1)*x;return;}
    int mid=(l+r)>>1;
    pd(root,l,r);
    if(ql<=mid)add(ls(root),l,mid,ql,qr,x);
    if(qr>mid) add(rs(root),mid+1,r,ql,qr,x);
    up(root);
    return;
}
ll query(int root,int l,int r,int ql,int qr){
    if(ql<=l&&qr>=r)
        return a[root].sum;
    int mid=(l+r)>>1,ret=0;
    pd(root,l,r);
    if(ql<=mid)ret+=query(ls(root),l,mid,ql,qr);
    if(qr>mid)ret+=query(rs(root),mid+1,r,ql,qr);
    return ret;
}
int main()
{
    int n,m,opt,l,r,k,d,t;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>data[i];
    for(int i=n-1;i>0;i--)
        data[i+1]=data[i+1]-data[i];
    build(1,1,n);
    for(int i=0;i<m;i++){
        cin>>opt;
        if(opt==1){
            cin>>l>>r>>k>>d;
            add(1,1,n,l,l,k);
            if(l+1<=r)add(1,1,n,l+1,r,d);
            if(r<n)add(1,1,n,r+1,r+1,-(k+d*(r-l)));//注意这里加了判断
        }
        else{
            cin>>t;
            cout<<query(1,1,n,1,t)<<endl;
        }
        
    }
    return 0;
}