考试的时候打的这道题 硬是想了半天想不出来 回来一看觉得自己真的智慧
等差数列的意思是什么？ 在一个数列的第二项及以后 所有的项与前一项的差值相同
将这一点反应到差分数组中去
如
原数列： 0 0 0 0 0 0
等差数列： 1 3 5 7 9
现数列： 1 3 5 7 9 0
现等差数列 1 2 2 2 2 -9
那么如果我要对一个数列的 [l,r] 加上首项为 k 公差为 d 的等差数列
大概就像这样
| l | r | r+1 | |||
|---|---|---|---|---|---|
| k | d | d | d | d | -((r-l)*d+k) |
观察一下这样的操作 发现需要频繁的维护一段区间的同时也需要查询一段区间 因此考虑线段树
因为所有操作只涉及到加法，普通线段树即可解决
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define int long long
int n,m;
int a[N];
int l,r,k,d;
struct node{
int val=0,addt=0;
}tr[N<<2];
inline int read()
{
int x=0;
bool f=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
f=0;
for(;isdigit(ch);ch=getchar())
x=(x<<1)+(x<<3)+ch-'0';
return f?x:(~(x-1));
}
void pushup(int x)
{
tr[x].val=tr[x<<1].val+tr[x<<1|1].val;
}
void pushdown(int x,int cl,int cr)
{
int cmid=(cl+cr)>>1;
tr[x<<1].val+=tr[x].addt*(cmid-cl+1);
tr[x<<1|1].val+=tr[x].addt*(cr-cmid);
tr[x<<1].addt+=tr[x].addt;
tr[x<<1|1].addt+=tr[x].addt;
tr[x].addt=0;
}
void update(int l,int r,int val,int x=1,int cl=1,int cr=n)
{
if(cl>=l&&cr<=r)
{
tr[x].val+=val*(cr-cl+1);
tr[x].addt+=val;
return ;
}
int cmid=(cl+cr)>>1;
pushdown(x,cl,cr);//经过了x点 顺便把它下放了
if(l<=cmid)
{
update(l,r,val,x<<1,cl,cmid);
}
if(r>cmid)
{
update(l,r,val,x<<1|1,cmid+1,cr);
}
pushup(x);//!!!!!!!!!!!!!!
}
int query(int l,int r,int x=1,int cl=1,int cr=n)
{
if(cl>=l&&cr<=r)
{
return tr[x].val;
}
int cmid=(cl+cr)>>1;
pushdown(x,cl,cr);//经过了x点 顺便把它下放了
if(l>cmid)
{
return query(l,r,x<<1|1,cmid+1,cr);
}
else if(r<=cmid)
{
return query(l,r,x<<1,cl,cmid);
}
else
return query(l,r,x<<1,cl,cmid)+query(l,r,x<<1|1,cmid+1,cr);
}
void build(int x,int cl,int cr)
{
if(cl==cr)//到达了叶子结点
{
tr[x].val=a[cl];
return ;
}
int cmid=(cl+cr)>>1;
build(x<<1,cl,cmid);
build(x<<1|1,cmid+1,cr);
pushup(x);//'递 '完成后开始'归 '（上传）
}
main()
{
n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=n-1;i>0;i--)a[i+1]-=a[i];//构建差分数组
build(1,1,n);
for(int i=1;i<=m;i++)
{
l=read();
if(l==1)
{
l=read();r=read();k=read();d=read();
update(l,l,k);
if(l+1<=r)update(l+1,r,d);
if(r<n)update(r+1,r+1,-(k+(r-l)*d));
}
else
{
l=read();
cout<<query(1,l)<<endl;
}
}
return 0;
}