社区讨论
线段树板子,0pts,求大佬帮调,悬关!
P3372【模板】线段树 1参与者 5已保存回复 9
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 8 条
- 当前快照
- 1 份
- 快照标识符
- @mdmjp91j
- 此快照首次捕获于
- 2025/07/28 11:25 7 个月前
- 此快照最后确认于
- 2025/11/04 03:37 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,mid,a[100005],xx,yy,zz,uu;
struct str{
int lch,rch,lazy;
long long val;
}tree[400005];
//更新节点
inline void update(int x) {tree[x].val=tree[x*2].val+tree[x*2+2].val+tree[x].lazy;}
//建树
inline void build(int x,int l,int r)
{
tree[x].lch=l;
tree[x].rch=r;
if(l==r)
{
tree[x].val=a[x];
return ;
}
mid=(l+r)>>1;
build(2*x,l,mid);
build(2*x+1,mid+1,r);
}
//单点修改/查询
inline void change(int k,int x,int y)
{
if(tree[k].lch==tree[k].rch)
{
tree[k].val=y;
return ;
}
mid=(tree[k].lch+tree[k].rch)>>1;
if(x<=mid) change(k*2,x,y);
else change(k*2+1,x,y);
update(k);//注意:一定一定要修改当前节点的值
}
//区间修改(以区间加法为例)
inline void changes(int k,int l,int r,int x)
{
if(tree[k].lch==l&&tree[k].rch==r)
{
tree[k].val+=(r-l+1)*x;
tree[k].lazy+=x;
return ;
}
mid=(tree[k].lch+tree[k].rch)>>1;
if(r<=mid) changes(k*2,l,r,x);
else if(l>mid) changes(k*2+1,l,r,x);
else
{
changes(k*2,l,mid,x);
changes(k*2+1,mid+1,r,x);
}
update(k);//更新数据
}
//下传标记(当标记是绝对标记的时候需要下传)
inline void down(int x)
{
if(tree[x].lch==tree[x].rch)//叶子节点
{
tree[x].lazy=0;
return ;
}
tree[x*2].val+=(tree[x*2].rch-tree[x*2].lch+1)*tree[x].lazy;
tree[x*2+1].val+=(tree[x*2+1].rch-tree[x*2+1].lch+1)*tree[x].lazy;
tree[x*2].lazy+=tree[x].lazy;
tree[x*2+1].lazy+=tree[x].lazy;
tree[x].lazy=0;//想办法让该懒标记不影响正确答案(根据答案的性质来进行修改)
}
//区间查询
inline long long asks(int x,int l,int r)
{
if(tree[x].lazy) down(x);
if(tree[x].lch==tree[x].rch) return tree[x].val;
mid=(tree[x].lch+tree[x].rch)>>1;
if(r<=mid) return asks(x*2,l,r);
else if(l>mid) return asks(x*2+1,l,r);
else return asks(x*2,l,mid)+asks(x*2+1,mid+1,r);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%d",&xx);
if(xx==1)
{
scanf("%d%d%d",&yy,&zz,&uu);
changes(1,yy,zz,uu);
}
else
{
scanf("%d%d",&yy,&zz);
printf("%lld\n",asks(1,yy,zz));
}
}
return 0;
}
回复
共 9 条回复,欢迎继续交流。
正在加载回复...