题解 P1438 【无聊的数列】

· · 题解

daolao们写的题解本juruo表示看不懂....

在这里发个好理解的（我觉得）

其实就是个线段树区间修改加区间查询的模板题 精髓在于维护差分数组b[i] 下面直接上代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[1023654],b[1023654];//原始数组a[i]和差分数组b[i];
struct tree{
    int l,r;
    long long WOW,add;
}t[1000000*4+1];
bool flag;
void build(int p,int l,int r)//建树;
{
    t[p].l=l,t[p].r=r;
    if(l==r)
    {
        t[p].WOW=b[l];//用差分数组建树;
        return;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].WOW=t[p*2].WOW+t[p*2+1].WOW;
}
void spread(int p)//延迟标记;
{
    if(t[p].add)
    {
        t[p*2].WOW+=t[p].add*(t[p*2].r-t[p*2].l+1);
        t[p*2+1].WOW+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
        t[p*2].add+=t[p].add;
        t[p*2+1].add+=t[p].add;
        t[p].add=0;
    }
}
void change(int p,int l,int r,int D)//区间修改的模板;
{
    if(t[p].l>=l&&t[p].r<=r)
    {
        t[p].WOW+=(long long)D*(t[p].r-t[p].l+1);
        t[p].add+=D;
        return;
    }
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(mid>=l) change(p*2,l,r,D);
    if(mid<r) change(p*2+1,l,r,D);
    t[p].WOW=t[p*2].WOW+t[p*2+1].WOW;
}
int query(int p,int l,int r)//区间查询的模板;
{
    if(t[p].l>=l&&t[p].r<=r)
    {
        return t[p].WOW;
    }
    long long ans=0; 
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(mid>=l) ans+=query(p*2,l,r);
    if(mid<r) ans+=query(p*2+1,l,r);
    return ans;
}
void Read()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        b[i]=a[i]-a[i-1];//处理差分数组;
    }
    build(1,1,n);
    int t,l,r,k,d;
    for(int i=1;i<=m;i++)
    {
        cin>>t;
        if(t==1)
        {
            cin>>l>>r>>k>>d;
            change(1,l,l,k);//单点修改与区间修改
            if(r>l) change(1,l+1,r,d);//放在同一个函数中
            if(r!=n) change(1,r+1,r+1,-(k+(r-l)*d));
        }//利用差分数组性质完成题目要求;
        if(t==2)
        {
            cin>>l;
            cout<<query(1,1,l)<<endl;//查询差分数组前缀和以达到
        }                   //求单点值的目的;
    }
}
int main(){
    Read();//个人习惯
    return 0;
}