[luogu P1438] 无聊的数列
题目背景
无聊的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）。
输出格式：
对于每个询问，输出答案，每个答案占一行。
输入输出样例
5 2 1 2 3 4 5 1 2 4 1 2 2 3
6
说明
数据规模：
0≤n，m≤100000
|a[i]|，|K|，|D|≤200
Hint：
有没有巧妙的做法？
纯粹是为了刷zkw线段树才看这题的。。（标签打着zkw我也没办法）
zkw是一种很棒棒的线段树，将冗长的代码（还是zkw清真）压得很短，还是非递归的，常数小，空间小，效率高！
但是。。。
这一题花了本蒟蒻两个下午+一个晚上的时间（悲剧），可能是因为我实在太菜了吧，旁边xtx一眼用bit秒掉了这题（%%%）。
好吧，我承认用了与sol里面都不同的方法（因为我要练zkw啊！！！）
因为我太菜了，不会bit，不会lazy，所以只能打打zkw了。。
我是这样想的——
由于区间修改时，直接上去用数据结构修改是一件很麻烦的事情，那怎么办？
设原数组为o[1..n]，设a[1]=o[1]，a[2]=o[2]-o[1]...（dalao们一定都看出来了，这是差分数组）
这样，修改就变成了：
a[l]+=k，a[l+1..r]+=d，a[r+1]-=k+(r-l)*d
但是。。仍然需要区间修改。。。怎么办？再差分！
设b[1]=a[1]，b[2]=a[2]-a[1]...
这样，修改又变成了：
b[l]+=k，b[l+1]+=d，b[r]-=k+(r-l+1)*d，b[r+1]+=k+(r-l)*d（别看就几个式子，当时的我意识模糊推了好久）
显然，我们现在只需要单点修改了，是不是很高兴！！！
然而，查询怎么办？
推一推。。。
o[x]=a[1]+a[2]+...+a[x]=b[1]+b[1]+b[2]+b[1]+b[2]+b[3]+...+b[1]+b[2]+..+b[x]=x*b[1]+(x-1)*b[2]+...+1*b[x]
这怎么办？
o[x]=(x+1)*(b[1]+b[2]+..+b[x])-(1*b[1]+2*b[2]+..+x*b[x])
好像可以了。。。我们发现，我们还需要在维护一个w数组其中w[i]=i*b[i]。
然后，询问操作就变成了区间修改，或者说更简单的区间修改（前缀和）。。
code：
#include<bits/stdc++.h>
#define LL long long
#define id(x) (m+x-1)
using namespace std;
;
int n,m,Q; LL o[N],b[N],w[N];
void B() {
; i<=n; i++) scanf("%lld",&o[i]);
; m<=n+; m<<=) ;
}
void U(int x,LL v) {
)>>=; x; x>>=)
b[x]=b[x<<]+b[x<<|],w[x]=w[x<<]+w[x<<|];
}
LL A(int x) {
LL ret=o[x];
; i!=; i>>=)
) ret+=b[i^]*(x+)-w[i^];
return ret;
}
int main() {
scanf("%d%d",&n,&Q),B();
; i<=Q; i++) {
int c,l,r,k,d; scanf("%d",&c);
) {
scanf("%d%d%d%d",&l,&r,&k,&d);
U(l,k),U(l+,d-k);
U(r+,(LL)(-k)-(LL)(r-l+)*d),U(r+,(LL)k+(LL)(r-l)*d);
} else scanf("%d",&k),printf("%lld\n",A(k));
}
;
}然后，终于tmA掉了。。qwq
垃圾zkw，毁我青春 zkwdalao这么强，当然要%一%啦~~~