社区讨论
哪位大佬能救救我,10分线段树!!!!
P3372【模板】线段树 1参与者 5已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mi6ml5dj
- 此快照首次捕获于
- 2025/11/20 07:20 4 个月前
- 此快照最后确认于
- 2025/11/20 07:20 4 个月前
CPP
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
long long a[100001];
long long add[400010],tree[400010];
void make_tree(int k,int le,int ri)
{
if(le==ri)
{
tree[k]=a[ri];
return;
}
int mid=(le+ri)/2;
make_tree(k*2,le,mid);
make_tree(k*2+1,mid+1,ri);
tree[k]=tree[k*2]+tree[k*2+1];
}
void mark(int k,int le,int ri,int a,int b,int addx)
{
if(add[k]!=0)
{
add[k*2]+=add[k];
add[k*2+1]+=add[k];
int midx=(le+ri)/2;
tree[k*2]+=(midx-le+1)*add[k];
tree[k*2+1]+=(ri-midx)*add[k];
add[k]=0;
return;
}
if(le>b||ri<a) return;
else if(le>=a&&ri<=b)
{
tree[k]+=(ri-le+1)*addx;
add[k]+=addx;
return;
}
else
{
if(le>=a&&ri>b&&le<=b) tree[k]+=(b-le+1)*addx;
if(le<a&&ri>=a&&ri<=b) tree[k]+=(ri-a+1)*addx;
if(le<a&&ri>b) tree[k]+=(b-a+1)*addx;
int mid=(le+ri)/2;
mark(k*2,le,mid,a,b,addx);
mark(k*2+1,mid+1,ri,a,b,addx);
}
}
long long sum;
void sumx(int k,int le,int ri,int a,int b)
{
if(add[k]!=0)
{
add[k*2]+=add[k];
add[k*2+1]+=add[k];
int midx=(le+ri)/2;
tree[k*2]+=(midx-le+1)*add[k];
tree[k*2+1]+=(ri-midx)*add[k];
add[k]=0;
}
if(le>b||ri<a)
{
return;
}
else if(le>=a&&ri<=b)
{
sum+=tree[k];
return;
}
int mid=(le+ri)/2;
sumx(k*2,le,mid,a,b);
sumx(k*2+1,mid+1,ri,a,b);
}
int main()
{
// freopen("luogu3372.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
make_tree(1,1,n);
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
if(x==1)
{
int y,z,u;
scanf("%d%d%d",&y,&z,&u);
mark(1,1,n,y,z,u);
}
if(x==2)
{
int y,z;
sum=0;
scanf("%d%d",&y,&z);
sumx(1,1,n,y,z);
printf("%lld\n",sum);
}
}
return 0;
}
回复
共 7 条回复,欢迎继续交流。
正在加载回复...