P1438

MichaelYoung · 2019-08-10 20:04:27 · 题解

我太弱了，根本看不懂大佬们的差分式的的思路，就只好用一种复杂的方法来写。

但仍是线段树！

我设了三个数组，分别用来表示rt管辖的区间的第一个数，这个区间被加上的等差数列（还没向下传给他的儿子们）的首项，以及公差。 主要注意下rt<<1和rt<<1|1的区别就行了。

上代码

//1438
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=100000+5;
int first[maxn<<2],one[maxn<<2],tol[maxn<<2],bj[maxn<<2];
int a[maxn];
int ans=0;
void pushup(int rt)
{
    first[rt]=first[rt<<1];
}
void build(int rt,int l,int r)
{
    if(l==r)
    {
        first[rt]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}
void pushdown(int rt,int l,int r)
{
    int mid=(l+r)>>1;
    first[rt<<1]=first[rt];
    first[rt<<1|1]+=(one[rt]+(mid+1-l)*tol[rt]);
    one[rt<<1]+=one[rt];
    tol[rt<<1]+=tol[rt];
    one[rt<<1|1]+=(one[rt]+tol[rt]*(mid+1-l));
    tol[rt<<1|1]+=tol[rt];
    tol[rt]=0;
    one[rt]=0;
}
void update(int rt,int l,int r,int L,int R,int del,int k)
{
    if(l>R||r<L)return;
    if(L<=l&&r<=R)
    {
        first[rt]+=(k+del*(l-L));
        tol[rt]+=del;
        one[rt]+=(k+del*(l-L));
        return;
    }
    int mid=(l+r)>>1;
    pushdown(rt,l,r);
    update(rt<<1,l,mid,L,R,del,k);
    update(rt<<1|1,mid+1,r,L,R,del,k);
    pushup(rt);
}
void query(int rt,int l,int r,int L,int R,int k)
{
    if(l>R||r<L)return;
    if(L<=l&&r<=R)
    {
        ans=first[rt];
        return;
    }
    int mid=(l+r)>>1;
    pushdown(rt,l,r);
    query(rt<<1,l,mid,L,R,k);
    query(rt<<1|1,mid+1,r,L,R,k);
    pushup(rt);
}
int main()
{
    //freopen("1438.in","r",stdin); freopen("out.txt","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    int order,l,r,del,k;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&order);
        if(order==1)
        {
            scanf("%d%d%d%d",&l,&r,&k,&del);
            update(1,1,n,l,r,del,k);
        }
        else
        {
            ans=0;
            int p;
            scanf("%d",&p);
            query(1,1,n,p,p,k);
            printf("%d\n",ans);
        }
    }
    return 0;
}