无聊的数列

题目背景

无聊的YYB总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的YYB想出了一道无聊的题：无聊的数列。。。（K峰：这题不是傻X题吗）

题目描述

维护一个数列{a[i]}，支持两种操作：

1、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、2 P：询问序列的第P个数的值a[P]。

输入输出格式

输入格式：

第一行两个整数数n，m，表示数列长度和操作个数。

第二行n个整数，第i个数表示a[i]（i=1,2,3…,n）。

接下来的m行，表示m个操作，有两种形式：

1 L R K D

2 P 字母意义见描述（L≤R）。

输出格式：

对于每个询问，输出答案，每个答案占一行。

输入输出样例

输入样例#1：

5 2
1 2 3 4 5
1 2 4 1 2
2 3

输出样例#1：

6

说明

数据规模：

0≤n，m≤100000

|a[i]|，|K|，|D|≤200

Hint：

有没有巧妙的做法？

思路

zkw线段树

标记永久化；

永久化的标记就是值；

——zkw

同样的区间改值；

同样的标记位置；

不用下传！

由底向上；

遇到标记按规则变动；

tl存线段的左端点的位置，tk存线段的左端点的值，td存等差数列的公差；

代码实现

#include<cstdio>
const int maxn=1<<19;
int n,q,m;
int a,b,c,d,e;
int tl[maxn],tk[maxn],td[maxn];
void build(){for(int i=m;i>0;i--) tl[i]=tl[i<<1];}
void change(int L,int R,int k,int d){
    for(int l=L+m-1,r=R+m+1;l^r^1;l>>=1,r>>=1){
        if(l&1^1) tk[l^1]+=k+(tl[l^1]-L)*d,td[l^1]+=d;
        if(r&1) tk[r^1]+=k+(tl[r^1]-L)*d,td[r^1]+=d;
    }
}
int search(int p,int ret){
    for(int i=m+p;i>=1;i>>=1) ret+=tk[i]+(p-tl[i])*td[i];
    return ret;
}
int main(){
    scanf("%d%d",&n,&q);
    for(m=1;m<=n;m<<=1);
    for(int i=1;i<=n;i++) scanf("%d",&tk[m+i]),tl[m+i]=i;
    build();
    while(q--){
        scanf("%d",&a);
        if(a==1){
            scanf("%d%d%d%d",&b,&c,&d,&e);
            change(b,c,d,e);
        }
        if(a==2){
            scanf("%d",&b);
            printf("%d
",search(b,0));
        }
    }
    return 0;
}