社区讨论

query不输出求条

P3372【模板】线段树 1参与者 4已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@mjp2x9tj
此快照首次捕获于
2025/12/28 09:57
2 个月前
此快照最后确认于
2025/12/31 12:50
2 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define I_don_t_want_to_AFO int main()
#define I_want_to_study_OI_forever return 0;
using namespace std;
long long n,m,a[100005];
struct node{
	int l,r;
	long long val,tag;
}tr[400005]; 

void push_up(int u){
	tr[u].val=tr[u<<1].val+tr[u<<1|1].val;
}

void push_down(int u){
	if(tr[u].tag){
		tr[u<<1].val+=(tr[u<<1].r-tr[u<<1].l+1)*tr[u].tag;
		tr[u<<1].tag+=tr[u].tag;
		
		tr[u<<1|1].val+=(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].tag;
		tr[u<<1|1].tag+=tr[u].tag;
		
		tr[u].tag=0;
	}
}

void build(int u,int l,int r){
	tr[u].l=l;
	tr[u].r=r;
	tr[u].tag=0;
	if(l==r){
		tr[u].val=a[u];
		return;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	push_up(u);
}

long long query(int u,int ql,int qr){
	cout<<u<<" "<<"123456789123456789123456789\n";
	if(tr[u].l>=ql&&tr[u].r<=qr){
		return tr[u].val;
	}
	push_down(u);
	int mid=tr[u].l+tr[u].r>>1;
	long long res=0;
	if(ql<=mid){
		res+=query(u<<1,ql,qr);
	}
	if(qr>mid){
		res+=query(u<<1|1,ql,qr);
	}
	return res;
}

void change(int u,int ql,int qr,int d){
	if(tr[u].l>=ql&&tr[u].r<=qr){
		tr[u].val+=(tr[u].r-tr[u].l+1)*d;
		tr[u].tag+=d;
	}
	push_down(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(ql<=mid){
		change(u<<1,ql,qr,d);
	}
	if(qr>mid){
		change(u<<1|1,ql,qr,d);
	}
	push_up(u);
} 


I_don_t_want_to_AFO{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	
	build(1,1,n);
//	cout<<"3112";
	while(m--){
		int op,x,y,z;
		cin>>op>>x>>y;
		if(op==1){
			cin>>z;
			change(1,x,y,z);
		}else{
			cout<<query(1,x,y);
		}
		

	}
	I_want_to_study_OI_forever
}

rt

回复

11 条回复,欢迎继续交流。

正在加载回复...