题解 P1438

Provicy · 2019-09-29 20:06:22 · 题解

这是我AC的第一道非模板的线段树，故本题解写的不好请大家见谅。

其实这道题就是要实现用等差数列的方式修改一个区间。因为等差数列每一项之间的差都相等，所以我们想到可以用差分的思想去修改这个区间。我们用cf数组来记录这个差分。

那么对于一个[l,r]的区间修改，根据我们以前的差分经验，我们就需要实现以下三个操作：

完成这样的修改操作时，每次我们查询a[p]的值时，只需将a[p]加上从序列开始第1个点到这个点的差分值和即可，其实就是一个区间求和

掌握上述知识后，我们就可以打出这个线段树的代码了：

#include <bits/stdc++.h>
using namespace std;
const int N=410000;
int n,m,a[N],cf[N],flag[N];
inline int LeftChild(int x){return x<<1;}
inline int RightChild(int x){return x<<1|1;}
inline void Up(int x){cf[x]=cf[LeftChild(x)]+cf[RightChild(x)];}
inline void Add(int x,int l,int r,int k){flag[x]+=k;cf[x]+=(r-l+1)*k;}
void Push_Down(int x,int l,int r)
{
    Add(LeftChild(x),l,(l+r)>>1,flag[x]);
    Add(RightChild(x),((l+r)>>1)+1,r,flag[x]);
    flag[x]=0;
}
void UpDate(int u,int v,int l,int r,int x,int k)//区间修改
{
    if(l>=u&&r<=v)
    {
        Add(x,l,r,k);
        return;
    }
    Push_Down(x,l,r);
    if(u<=(l+r)>>1) UpDate(u,v,l,(l+r)>>1,LeftChild(x),k);
    if(v>(l+r)>>1) UpDate(u,v,((l+r)>>1)+1,r,RightChild(x),k);
    Up(x);
}
int Ask(int u,int v,int l,int r,int x)//区间求和
{
    if(l>=u&&r<=v) return cf[x];
    int ans=0;Push_Down(x,l,r);
    if(u<=(l+r)>>1) ans+=Ask(u,v,l,(l+r)>>1,LeftChild(x));
    if(v>(l+r)>>1) ans+=Ask(u,v,((l+r)>>1)+1,r,RightChild(x));
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1,to,l,r,k,d,p;i<=m;i++)
    {
        scanf("%d",&to);
        if(to==1)//差分思想
        {
            scanf("%d%d%d%d",&l,&r,&k,&d);UpDate(l,l,1,n,1,k);
            if(r>l) UpDate(l+1,r,1,n,1,d);//特判这个区间是不是只有一个点
            if(r!=n) UpDate(r+1,r+1,1,n,1,-k-(r-l)*d);//如果r==n了，那么就没有需要减去的东西了
        }
        if(to==2) scanf("%d",&p),printf("%d\n",a[p]+Ask(1,p,1,n,1));
    }
    return 0;
}