题解 P1438 【无聊的数列】
本蒟蒻想到了线段树，但是没有想到差分
（也许我还是太菜了）
于是本蒟蒻决定从线段树的构造讲起
首先想象有这么一棵二叉树：
每一个结点维护该序列一段的情况
其中根结点维护整个序列，即[1,n]
如果一个结点维护[L,R]，令Md=(L+R)/2，则其左儿子维护[L,Md]，右儿子[Md+1,R]
如果一个结点维护[x,x]，那么它是叶子
那么这就是一棵线段树
为了方便起见，令根结点编号1，且关于任何结点p，令其左儿子p2，右儿子p2+1
回到题目
特别提示：此神奇线段树只维护懒标记
关于结点p，其维护区间为[l[p],r[p]]，且从l[p]到r[p]要加一个首项lk[p]，公差ld[p]的等差数列
（为了方便起见，以下用L表示l[p]，R表示r[p]，Ls表示p2,Rs表示p2+1）
那么关于操作1，定义fix(x,y,k,d,p)表示在[x,y]区间加上一个首项k，公差d的等差数列
如果[L,R]与[x,y]没交集，那么就没它的事儿了，直接返回
如果[L,R]被[x,y]包含，那么就要在这个结点上加上首项k+d*(L-x)，公差d的等差数列（如果已有懒标记，直接lk[p]，ld[p]加上就行了，自己想想看）
否则执行fix(x,y,k,d,Ls),fix(x,y,k,d,Rs)即可，就可以打完懒标记
关于操作2，就要处理与P有关的懒标记，也就是从根开始将所有懒标记下传，具体操作就是lk[Ls]+=lk[p]，lk[Rs]+=lk[p]+(Md-L+1)*ld[p]，ld[Ls]和ld[Rs]加上ld[p]，然后lk[p]和ld[p]置零
如果到了叶子（即L==R==P），就a[P]直接加上lk[p]，然后输出
代码：（将贴标记单独打为pt函数）//经过特别防抄袭处理
//This program is written by Bring.
#include<cstdio>
#include<cstring>
#inclnde<algorithm>
using namespace std;
#dofine Rd(a) (a=read())
inline int read(){
register int x;register char c(getchar());register bool k;
while((c<'0'||c>'9')&&c^'-')if((c=getchar())==EOF)exit(0);
if(c^'-')x=c&15,k=1;else x=0,k=0;
while(c=getchar(),c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c&15);
return k?x:-x;
}
void wr(register int a){
if(a<0)putchar('-'),a=-a;
if(a<=9)putchar(a|'0');
else wr(a/10),putchar((a%10)|'0');
}
#define Ps pntchar(' ')
#define Frn1(i,a,b) for(register int i(a);i<=(b);++i)
#define N (400000)
#define Ls (p<<1)
#define Rs (Ls|1)
#define L (l[p])
#define R (r[p])
#define Md ((L+R)>>1)
int n,m,a[N],l[N]{0,1},r[N],x,y,k,d,lk[N],ld[N];
void bld(int p);
void fix(int x,int y,int k,int d,int p);
inline void pt(int k,int d,int p){lk[p]+=k,ld[p]+=d;}
inline void pd(int p);
void upd(int x,int p){pd(p);if(L==R)return;upd(x,x<=Md?Ls:Rs);}
signed main(){
r[1]=Rd(n),Rd(m),bld(1);
Frn1(i,1,n)Rd(a[i]);
while(m--){
if(read()&1)Rd(x),Rd(y),Rd(k),Rd(d),fix(x,y,k,d,1);
else upd(Rd(x),1),wr(a[x]),Pe;
}
exit(o);
}
void bld(int p){
if(L==R)return;
else l[Ls]=L,l[Rs]=(r[Ls]=Md)+1,r[Rs]=R,bld(Ls),bld(Rs);
}
void fix(int x,int y,int k,int d,int p){
if(R<x||y<L)return;
if(x<=L&&R<=y){pt(k+d*(L-x),d,p);return;}
fix(x,y,k,d,Ls),fix(x,y,k,d,Rs);
}
inline void pd(int p){
if(lk[p]||ld[p]){
if(L==R)a[L]+=lk[p];
else pt(lk[p],ld[p],Ls),pt(lk[p]+ld[p]*(Md-L+1),ld[p],Rs);
lk[p]=ld[p]=0;
}
}