lcy_123 @ 2023-04-15 16:21:46
敲了一下午键盘,没找到问题在哪,样例都过不了 (注释可能有点问题...)
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[200005],lazy_tag[200005],ans[200005];
inline int read()//快读
{
register int s=0,w=1;
register 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;
}
int ls(int x)//当前节点左儿子编号:2*x
{
return x/2;
}
int rs(int x)//当前节点右儿子编号:2*x+1
{
return x/2+1;
}
void push_up(int pos)//节点回溯,答案记录为左右儿子之和
{
ans[pos]=ans[ls(pos)]+ans[rs(pos)];
}
void build(int l,int r,int pos)//建树
{
lazy_tag[pos]=0;
if(l==r)//左右儿子相同,为叶子节点,赋值
{
ans[pos]=a[l];
return;
}
int mid=(l+r)/2;//二分向下搜索叶子节点
build(l,mid,ls(pos));//左边:l~mid
build(mid+1,r,rs(pos));//右边:mid+1~r
push_up(pos);//回溯,进行答案的维护
}
void sum(int pos,int l,int r,int add)//记录当前节点所代表的区间
{
ans[pos]+=add*(r-l+1);//改变整个区间,加上元素个数个值
lazy_tag[pos]+=add;
}
void push_down(int pos,int l,int r)
{
int mid=(l+r)/2;//二分记录两边子节点
sum(ls(pos),l,mid,lazy_tag[pos]);//左儿子
sum(rs(pos),mid+1,r,lazy_tag[pos]);//右儿子
lazy_tag[pos]=0;
}
void update(int dl,int dr,int l,int r,int pos,int add)//区间修改
{
//dl,dr为修改区间,add是修改的值
if(dl<=l&&r<=dr)//当前区间整个在修改区间内,修改整个区间
{
ans[pos]+=add*(r-l+1);//和sum函数内一样
lazy_tag[pos]+=add;
return ;
}
push_down(pos,l,r);//向下传导lazy_tag
int mid=(l+r)/2;//二分往左右儿子传导
if(dl<=mid)update(dl,dr,l,mid,ls(pos),add);//左边
if(dr>mid)update(dl,dr,mid+1,r,rs(pos),add);//右边
push_up(pos);//向上回溯
}
int ask(int dl,int dr,int l,int r,int pos)//区间询问
{
//dl,dr为询问区间
int tot=0;//询问的答案
if(dl<=l&&r<=dr)return ans[pos];//当前区间整个在询问区间内,返回整个区间的答案
push_down(pos,l,r);//将lazy_tag向下传导完
int mid=(l+r)/2;//左右查找区间
if(dl<=mid)tot+=ask(dl,dr,l,mid,ls(pos));//左边,答案累加
if(dr>mid)tot+=ask(dl,dr,mid+1,r,rs(pos));//右边,答案累加
return tot;
}
signed main()
{
n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
build(1,n,1);
for(int i=1;i<=m;i++)
{
int b=read();
if(b==1)
{
int x=read(),y=read(),add=read();
update(x,y,1,n,1,add);
}
else
{
int x=read(),y=read();
cout<<ask(x,y,1,n,1)<<endl;
}
}
}
by piasticOuO @ 2023-04-15 16:37:58
子节点应该是*2而不是/2吧?
by lcy_123 @ 2023-04-15 16:40:05
@piasticOuO 哦哦哦,注释都写了打错了,眼睛是真的花了,谢谢dalao
awa