题目描述

维护一个数列${a[i]}$，支持两种操作：
1、$ L, R, K, D$：给出一个长度等于$R-L+1$的等差数列，首项为$K$，公差为$D$，并将它对应加到$a[L]~a[R]$的每一个数上。即：令$a[L]=a[L]+K$，$a[L+1]=a[L+1]+K+D+….+a[L+2]=a[L+2]+K+2D……a[R]=a[R]+K+(R-L)D$
2、 $P$：询问序列的第$P$个数的值$a[P]$。

解决方案

其实我已开始看到题我又是一脸懵逼：
什么？？？等差数列？？这怎么维护？？？
分块？？不行吧？？
然后。。我参考了题解，因为差分我的真的没什么经验，我没怎么碰到过这种题；
因为等差数列易知$a[i]-a[i-1]=d$是定值；
利用差分前缀和的思想

一求前缀和，就可以发现刚好l-r能加上等差数列了！
要求$a[x]$,直接输出$data[i]+sum[1]+sum[2]+…+sum[x]$;
于是就变成了线段树模板
普通的修改和查询
但是要注意一些细节，不要越界操作了

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define rson 2*p
#define lson 2*p+1
#define N 200000+100
using namespace std;
struct node
{
    int lt;
    int rt;
    int val;
    int sum;
}a[4*N];
int n,m,data[N],cha[N];
void pushup(int p)
{
   a[p].sum=a[2*p].sum+a[2*p+1].sum;
}
void build(int p,int l,int r)
{
    a[p].lt=l;
    a[p].rt=r;
    if(l==r){a[p].sum=0;return;}
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
   pushup(p);
}
void pushdown(int p)
{
     if(a[p].val!=0)
    {
        a[2*p].val+=a[p].val;
        a[2*p].sum+=(a[2*p].rt-a[2*p].lt+1)*a[p].val;
        a[2*p+1].val+=a[p].val;
        a[2*p+1].sum+=(a[2*p+1].rt-a[2*p+1].lt+1)*a[p].val;
        a[p].val=0;
    }

}
void update(int p,int l,int r,int d)
{
    if(a[p].lt==l&&a[p].rt==r){a[p].val+=d;a[p].sum+=(r-l+1)*d;return;}
    pushdown(p);
    int mid=(a[p].lt+a[p].rt)/2;
    if(r<=mid)update(2*p,l,r,d);
    else if(l>mid)update(2*p+1,l,r,d);
    else {update(2*p,l,mid,d);update(2*p+1,mid+1,r,d);}
   pushup(p);
}
int query(int p,int l,int r)
{
    if(a[p].lt==l&&a[p].rt==r)return a[p].sum;
    pushdown(p);
    int mid=(a[p].lt+a[p].rt)/2;
    if(r<=mid)return query(2*p,l,r);
    else if(l>mid)return query(2*p+1,l,r);
    else return query(2*p,l,mid)+query(2*p+1,mid+1,r);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&data[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int op,x,y,k,d;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d%d",&x,&y,&k,&d);
            if(x==y)//注意特判
            {
                update(1,x,y,k);
                if(x+1>n)continue;//注意不要越界
                update(1,x+1,x+1,-k);
                continue;
            }
            update(1,x+1,y,d);
            update(1,x,x,k);
            if(y+1>n)continue;//不要越界
            update(1,y+1,y+1,-(k+d*(y-x)));
        }
        else
        {
            scanf("%d",&x);
            printf("%d\n",data[x]+query(1,1,x));
        }

    }
    return 0;
}