QAQ一道线段树好题
题目大意：
给定一个有n个数的数列，共m种操作，有两种操作
1
l
r
k
d
1
l
r
k
d
表示将
a
[
l
]
a
[
l
]
~
a
[
r
]
a
[
r
]
的数加一个以k为首相，d为公差
2
x
2
x
表示求
a
[
x
]
a
[
x
]
是多少
QwQ又是一道不会的题
暴力修改肯定会T飞
如果可以用线段树进行区间修改呢？？
我们考虑，对于一段区间
[
l
,
r
]
[
l
,
r
]
，我们只需要记录它的区间的首相和公差，就能将这个标记下传了
QwQ哇，那可以只使用这个线段树进行一个标记下传了（所以没有up函数）
这里展示一下pushdown的部分
f
[
r
o
o
t
]
.
d
f
[
r
o
o
t
]
.
d
表示公差，
f
[
r
o
o
t
]
.
f
i
r
s
t
f
[
r
o
o
t
]
.
f
i
r
s
t
表示首相
void pushdown(int root,int l,int r)
{
if (f[root].d || f[root].first)
{
int mid = (l+r) >> 1;
f[2*root].d+=f[root].d;
f[2*root+1].d+=f[root].d;
f[2*root].first+=f[root].first;
f[2*root+1].first+=(f[root].first+(mid-l+1)*f[root].d);
f[root].d=f[root].first=0;
}
}因为，等差数列相加依然是等差数列，所以对于公差和首相，可以直接加
对一个区间的话
[
l
,
r
]
[
l
,
r
]
，
[
l
,
m
i
d
]
[
l
,
m
i
d
]
这部分可以直接进行加法，而对于
[
m
i
d
+
1
,
r
]
[
m
i
d
+
1
,
r
]
稍微操作一下，修改首相即可
求和什么的，也比较简单
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<vector>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int maxn = 100010;
struct Node{
int d,first;
};
Node f[4*maxn];
Node add[4*maxn];
int a[4*maxn];
int n,m;
void pushdown(int root,int l,int r)
{
if (f[root].d || f[root].first)
{
int mid = (l+r) >> 1;
f[2*root].d+=f[root].d;
f[2*root+1].d+=f[root].d;
f[2*root].first+=f[root].first;
f[2*root+1].first+=(f[root].first+(mid-l+1)*f[root].d);
f[root].d=f[root].first=0;
}
}
void update(int root,int l,int r,int x,int y,int first,int d)
{
if (x<=l && r<=y){
f[root].d+=d;
f[root].first+=(l-x)*d+first;
return ;
}
pushdown(root,l,r);
int mid = (l+r) >> 1;
if (x<=mid) update(2*root,l,mid,x,y,first,d);
if (y>mid) update(2*root+1,mid+1,r,x,y,first,d);
}
int query(int root,int l,int r,int pos)
{
if (l==r)
{
return a[l]+f[root].first;
}
pushdown(root,l,r);
int mid = (l+r) >> 1;
if (pos<=mid) return query(2*root,l,mid,pos);
if (pos>mid) return query(2*root+1,mid+1,r,pos);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<=m;i++)
{
int opt;
opt=read();
if (opt==1)
{
int l,r,k,d;
l=read(),r=read(),k=read(),d=read();
update(1,1,n,l,r,k,d);
}
else
{
int x=read();
printf("%d\n",query(1,1,n,x));.
}
}
return 0;
}