社区讨论

线段树板子,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 条回复,欢迎继续交流。

正在加载回复...