无聊的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：
有没有巧妙的做法？
思路：
我们可以用前缀和来表示第 i 位实际的数是多少。
当我们修改的时候，
[ l, r ] 首项 k， 公差 d，
一、 l 位加上 k，
二、（l ， r ] 加上 d，
三、r+1 加上 - (k + (r - l ) * d)
我们最后求 第 p 位的数的时候， 就是求和 1~p 然后在加上原来的数。
#include<bits/stdc++.h> #define ls (now << 1) #define rs (now << 1 | 1) using namespace std; const int N = 1e5+100; int a[N],n,m,l,r,k,d,p,op; long long val[N*4],tag[N*4]; void pushdown(int now, int l, int r){ if (!tag[now]) return; int mid = (l + r) >> 1; val[ls] += (mid - l) * tag[now]; val[rs] += (r - mid) * tag[now]; tag[ls] += tag[now]; tag[rs] += tag[now]; tag[now] = 0; } void build(int now, int l, int r){ if (l + 1 == r) return; int mid = (l + r) >> 1; build(ls,l,mid); build(rs,mid,r); } void Insert(int now, int l, int r, int a, int b, int w){ if (a <= l && b >= r - 1){ val[now] += (r - l) * w; tag[now] += w; return; } int mid = (l + r) >> 1; pushdown(now, l, r); if (a < mid) Insert(ls,l,mid,a,b,w); if (b >= mid) Insert(rs,mid,r,a,b,w); val[now] = val[ls] + val[rs]; } long long Query(int now, int l, int r, int a, int b){ long long ans = 0; if (a <= l && b >= r - 1){ return val[now]; } int mid = (l + r) >> 1; pushdown(now,l,r); if (a < mid) ans += Query(ls,l,mid, a,b); if (b >= mid) ans += Query(rs,mid,r,a,b); return ans; } int main(){ scanf("%d%d",&n,&m); for (int i = 1; i <= n; ++i) scanf("%d",&a[i]); build(1,1,n+1); for (int i = 0; i < m; ++i){ scanf("%d",&op); if (op == 1){ scanf("%d%d%d%d",&l,&r,&k,&d); Insert(1,1,n+1,l,l,k); if (l != r) Insert(1,1,n+1,l+1,r,d); if (r < n) Insert(1,1,n+1,r+1,r+1,-(k+(r-l)*d)); } else { scanf("%d",&p); long long ans = Query(1,1,n+1,1,p); printf("%lld\n",ans+a[p]); } } return 0; }
