社区讨论

#1~9 RE #10AC 求调

P13825【模板】线段树 1.5参与者 2已保存回复 3

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@mllc0jse
此快照首次捕获于
2026/02/14 04:20
5 天前
此快照最后确认于
2026/02/17 10:35
前天
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=1e6+10;
struct node{
	ll l,r;
	ll sum,add;
	int ls,rs;
}t[N*4];
int tot=0;//节点个数 
ll n,m;
void pushup(int k){
	t[k].sum=0;
	if(t[k].ls)t[k].sum+=t[t[k].ls].sum;
	if(t[k].rs)t[k].sum+=t[t[k].rs].sum;
}
int new_node(int l,int r){
	tot++,t[tot].l=l,t[tot].r=r;
	t[tot].sum=t[tot].add=0;
	t[tot].ls=t[tot].rs=0;
	return tot;
} 
void change(int k,ll v){
	t[k].sum+=(t[k].r-t[k].l+1)*v;
	t[k].add+=v;
}
void pushdown(int k){
	if(t[k].add==0)return;
	ll mid=(t[k].l+t[k].r)/2;
	if(t[k].ls==0)t[k].ls=new_node(t[k].l,mid);
	change(t[k].ls,t[k].add);
	if(t[k].rs==0)t[k].rs=new_node(mid+1,t[k].r);
	change(t[k].rs,t[k].add);
	t[k].add=0;
}
void update(int &k,int x,int y,ll v){
	if(k==0)k=new_node(1,n);
	if(t[k].r<x||t[k].l>y)return;
	if(t[k].l>=x&&t[k].r<=y){
		change(k,v);
		return;
	}
	pushdown(k);
	ll mid=(t[k].l+t[k].r)/2;
	if(x<=mid)update(t[k].ls,x,y,v);
	if(y>mid)update(t[k].rs,x,y,v);
	pushup(k);
}
ll query(int k,int x,int y){
	if(k==0)return 0;
	if(t[k].r<x||t[k].l>y)return 0;
	if(t[k].l>=x&&t[k].r<=y)return t[k].sum;
	pushdown(k);
	ll mid=(t[k].l+t[k].r)/2;
	ll res=0;
	if(x<=mid)res=query(t[k].ls,x,y);
	if(y>mid)res+=query(t[k].rs,x,y);
	return res;
}

int main(){
	cin>>n>>m;
	int root=0;
	while(m--){
		int op,l,r;
		ll k;
		cin>>op>>l>>r;
		if(op==1){
			cin>>k;
			update(root,l,r,k);
		}else{
			ll ys=(1LL*l+r)*(r-l+1)/2;
			ll zj=query(root,l,r);
			cout<<ys+zj<<"\n";
		}
	}
	return 0;
} 

回复

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

正在加载回复...