江宁12345678 @ 2023-03-28 21:52:02
#include<bits/stdc++.h>
using namespace std;
const int maxx=111111;
long long n,m,a[111111];
struct tree
{
int l,r;
long long pre,add;
};
tree t[4*maxx+2];
void bt(long long p,long long l,long long r)
{
t[p].l=l;
t[p].r=r;
if(l==r)
{
t[p].pre=a[l];
return;
}
long long mid=(l+r)/2;
bt(p*2,1,mid);
bt(p*2+1,mid+1,r);
t[p].pre=t[p*2].pre+t[p*2+1].pre;
}
void bjxc(long long p)
{
if(t[p].add!=0)
{
t[p*2].pre+=t[p].add*(t[p*2].r-t[p*2].l+1);
t[p*2+1].pre+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
t[p*2].add+=t[p].add;
t[p*2+1].add+=t[p].add;
t[p].add=0;
}
}
void qjxg(long long p,long long x,long long y,long long z)
{
if(x<=t[p].l&&y>=t[p].r)
{
t[p].pre+=(long long)z*(t[p].r-t[p].l+1);
t[p].add+=z;
return;
}
bjxc(p);
long long mid=(t[p].l+t[p].r)/2;
if(x<=mid)
{
qjxg(p*2,x,y,z);
}
if(y>mid)
{
qjxg(p*2+1,x,y,z);
}
t[p].pre=t[p*2].pre+t[p*2+1].pre;
}
long long ask(long long p,long long x,long long y)
{
if(x<=t[p].l&&y>=t[p].r)
{
return t[p].pre;
}
bjxc(p);
long long mid=(t[p].l+t[p].r)/2;
long long sum=0;
if(x<=mid)
{
sum+=ask(p*2,x,y);
}
if(y>mid)
{
sum+=ask(p*2+1,x,y);
}
return sum;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
bt(1,1,n);
for(int i=1;i<=m;i++)
{
long long cz;
cin>>cz;
if(cz==1)
{
long long x,y,k;
cin>>x>>y>>k;
qjxg(1,x,y,k);
}
if(cz==2)
{
long long x,y;
cin>>x>>y;
cout<<ask(1,x,y)<<endl;
}
}
return 0;
}
救命!!!
by Nephren_Sakura @ 2023-03-31 11:19:39
@江宁12345678
你下传的时候左右端点不动吗?
if(x<=mid)
{
qjxg(p*2,x,y,z);
}
if(y>mid)
{
qjxg(p*2+1,x,y,z);
}
改成
if(x<=mid)
{
qjxg(p*2,x,mid,z);
}
if(y>mid)
{
qjxg(p*2+1,mid+1,y,z);
}
ask 同理
by Nephren_Sakura @ 2023-03-31 11:20:53
@江宁12345678
bt也错了
是
bt(p*2,l,mid);
bt(p*2+1,mid+1,r);
by 江宁12345678 @ 2023-04-03 21:49:03
@_ChthollyNephren 谢大佬!
by 江宁12345678 @ 2023-04-03 22:13:06
@_ChthollyNephren 可是x和y是修改的区间不需要变吧
by Nephren_Sakura @ 2023-04-05 12:07:49
@江宁12345678
我去,我是傻逼
我们写法不同,我在写的时候下传了当前点的左右端点