瀛洲仙子 @ 2024-10-09 17:02:12
0pts
#include<bits/stdc++.h>
using namespace std;
typedef long long lld;
struct var
{
int l,r;//[l,r]
int lc,rc;
lld summ,tag;
var(){l=r=lc=rc=summ=tag=0;}
};var seg[300005];int cnt;
lld arr[100005];int n,m;
int build(int l,int r)
{
if(l==r)
{
seg[++cnt].summ=arr[l];
seg[cnt].l=seg[cnt].r=l;
return cnt;
}
seg[++cnt].l=l;seg[cnt].r=r;
int mid=(l+r)>>1;int k=cnt;
seg[cnt].lc=build(l,mid);
seg[k].rc=build(mid+1,r);
seg[k].summ=seg[seg[k].lc].summ+seg[seg[k].rc].summ;
return k;
}
void down(int id)
{
seg[seg[id].lc].tag=seg[seg[id].rc].tag=seg[id].tag;
seg[seg[id].lc].summ+=seg[id].tag*(seg[seg[id].lc].r-seg[seg[id].lc].l+1);
seg[seg[id].rc].summ+=seg[id].tag*(seg[seg[id].rc].r-seg[seg[id].rc].l+1);
seg[id].tag=0;return;
}
void add(int id,int l,int r,lld k)
{
if(seg[id].l>=l and seg[id].r<=r)
{seg[id].tag+=k;seg[id].summ+=k*(seg[id].r-seg[id].l+1);return;}
int mid=(seg[id].l+seg[id].r)>>1;down(id);
if(l<=mid)add(seg[id].lc,l,mid,k);
if(r>mid)add(seg[id].rc,mid+1,r,k);
seg[id].summ=seg[seg[id].lc].summ+seg[seg[id].rc].summ;
}
lld query(int id,int l,int r)
{
if(seg[id].l>=l and seg[id].r<=r)
return seg[id].summ;
int mid=(seg[id].l+seg[id].r)>>1;
down(id);lld ret=0;
if(l<=mid)
ret+=query(seg[id].lc,l,r);
if(r>mid)
ret+=query(seg[id].rc,l,r);
return ret;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>arr[i];
build(1,n);
int op,x,y;lld k;
/*for(int i=1;i<=cnt;++i)
printf("%d:[%d,%d],(%d,%d),{%d,%d}\n",i,seg[i].l,seg[i].r,seg[i].lc,
seg[i].rc,seg[i].summ,seg[i].tag);*/
while(m--)
{
int op;cin>>op;
if(op==1)
{
cin>>x>>y>>k;
add(1,x,y,k);
}
else
{
cin>>x>>y;
cout<<query(1,x,y)<<endl;
}
}
}
by Hagasei @ 2024-10-09 17:15:09
@瀛洲仙子
29 行改为
seg[seg[id].lc].tag+=seg[id].tag;
seg[seg[id].rc].tag+=seg[id].tag;
39,40 行改为
if(l<=mid)add(seg[id].lc,l,r,k);
if(r>mid)add(seg[id].rc,l,r,k);
by 瀛洲仙子 @ 2024-10-09 19:47:56
@Hagasei 感谢感谢 已通过 此贴完结