社区讨论
哪位大佬帮忙看看,谢谢!!!!
P3372【模板】线段树 1参与者 5已保存回复 8
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 8 条
- 当前快照
- 1 份
- 快照标识符
- @mi7yp65d
- 此快照首次捕获于
- 2025/11/21 05:47 4 个月前
- 此快照最后确认于
- 2025/11/21 05:47 4 个月前
#include
#include
#include
#include
using namespace std;
int n,m;
long long int a[100010];
const int maxn=100010;
struct segtreenode{
long long int val,lazytag;
}segtree[4maxn];
void build(long long int rt,long long int al,long long int ar)
{
segtree[rt].lazytag=0;
if(al==ar)
{
segtree[rt].val=a[al];
return ;
}
long long int m=(al+ar)/2;
build(rt2,al,m);
build(rt2+1,m+1,ar);
segtree[rt].val=segtree[rt2].val+segtree[rt2+1].val;
}//建树
void pushdown(long long int rt,long long int al,long long int ar)
{
long long int m=(al+ar)/2;
if(segtree[rt].lazytag!=0)
{
segtree[rt2].val+=segtree[rt].lazytag*(m-al+1);
segtree[rt2+1].val+=segtree[rt].lazytag(ar-m+1+1);
segtree[rt2].lazytag+=segtree[rt].lazytag;
segtree[rt2+1].lazytag+=segtree[rt].lazytag;
segtree[rt].lazytag=0;
}
}
void updata(long long int rt,long long int al,long long int ar,long long int ql,long long int qr,long long int val)
{
if(al>qr||ar<ql) return;
if(al>=ql&&ar<=qr)
{
segtree[rt].val+=(val*(ar-al+1));
segtree[rt].lazytag+=val;
return;
}
pushdown(rt,al,ar);
long long int m=(al+ar)/2;
updata(rt2,al,m,ql,qr,val);
updata(rt2+1,m+1,ar,ql,qr,val);
segtree[rt].val=segtree[rt2].val+segtree[rt2+1].val;
return;//增加一个值
}
long long int ans=0;
long long int query(long long int rt,long long int al,long long int ar,long long int ql,long long int qr)//查询
{
if(al>qr||ar<ql)
return 0;
if(al>=ql&&ar<=qr)
{
return segtree[rt].val;
}
pushdown(rt,al,ar);
long long int m=(al+ar)/2;
return query(rt2,al,m,ql,qr)+query(rt2+1,m+1,ar,ql,qr);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
}
build(1,1,n);
for(int i=1;i<=m;++i)
{
int num;
scanf("%d",&num);
if(num==1)
{
long long int ql,qr,val;
scanf("%lld%lld%lld",&ql,&qr,&val);
updata(1,1,n,ql,qr,val);;
}
if(num==2)
{
ans=0;
long long int ql,qr;
scanf("%lld%lld",&ql,&qr);
ans=query(1,1,n,ql,qr);
printf("%lld\n",ans);
}
}
return 0;
}
回复
共 8 条回复,欢迎继续交流。
正在加载回复...