题解 P1438 【无聊的数列】
流逝丶
2019-09-22 14:45:25
区间问题，肯定是线段树了，但是区间加的是一个等差数列，怎么办呢
我们可以通过差分来维护。
~~蛤是差分？~~
搞一个数组专门差分，在数组中记录对于$l-r$的区间加$x$，在l位置加上$x$，在$r+1$位置减去$x$。
当查询某个数值时，该位置上的数加上差分数组中$1$~该位置的前缀和，自己出组
数试一下发现这样是对的
我们线段树刚好可以区间修改和区间求和，所以这题要用到线段树维护差分
对于首项，我们在线段树的l位置直接加首项，在$(l+1)$~r位置区间修改，每个位置加上公差$d$，在$r+1$位置减去等差数组中
的最后一项也就是$a_1+(l-r)*d$，这样我们的区间加等差数列就维护好了。
单点查询时，查询线段树中1~$l$的值加上原数组中$a[l]$的值。
然后特别注意的是$r+1>n$的情况我们不必再修改，会$RE$
对于$l+1>r$的情况，只需在$l$位置加上首项，$l+1$位置减去首项。
然后这题就成了板子题了。
```cpp
#include<iostream>
#include<cstdio>
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
#define ls k<<1
#define rs k<<1|1
#define sum(rt) tr[rt].sum
#define laz(rt) tr[rt].laz
#define mid ((l+r)>>1)
using namespace std;
const int maxn=100005;
int n,m,a[maxn];
struct node{
int sum,laz;
}tr[maxn<<2];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
inline void update(int k){
sum(k)=sum(ls)+sum(rs);
}
inline void down(int k,int l,int r){
sum(ls)+=laz(k)*(mid-l+1);
laz(ls)+=laz(k);
sum(rs)+=laz(k)*(r-mid);
laz(rs)+=laz(k);
laz(k)=0;
}
void change(int k,int l,int r,int x,int y,int val){
if(x<=l&&y>=r){
sum(k)+=val*(r-l+1);
laz(k)+=val;
return ;
}
if(laz(k)!=0)down(k,l,r);
if(x<=mid)change(lson,x,y,val);
if(y>mid)change(rson,x,y,val);
update(k);
}
int ask(int k,int l,int r,int x,int y){
if(l==x&&y==r){
return sum(k);
}
if(laz(k)!=0)down(k,l,r);
if(y<=mid)return ask(lson,x,y);
else if(x>mid)return ask(rson,x,y);
else return ask(lson,x,mid)+ask(rson,mid+1,y);
}
int main(){
n=read();m=read();
for(int i=1;i<=n;++i)
a[i]=read();
int opt,l,r,k,d;
while(m--){
opt=read();
if(opt==1){
l=read();r=read();k=read();d=read();
change(1,1,n,l,l,k);
if(l!=r)change(1,1,n,l+1,r,d);
if(r+1<=n)change(1,1,n,r+1,r+1,-(k+(r-l)*d));
}
else {
l=read();
printf("%d\n",ask(1,1,n,1,l)+a[l]);
}
}
return 0;
}
```