求评价马蜂
  • 板块学术版
  • 楼主HeCao2008
  • 当前回复14
  • 已保存回复14
  • 发布时间2023/5/23 19:55
  • 上次更新2023/10/23 14:55:51
查看原帖
求评价马蜂
422996
HeCao2008楼主2023/5/23 19:55

有点标题党,实际是想要评价线段树模板,是不是够简洁(我是手残,打字打不快)清晰

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1014514;
int n,m,a[maxn],tree[maxn*4],tag[maxn*4];
int ls(int x){
	return x*2;
}
int rs(int x){
	return x*2+1;
}
void pushup(int x){
	tree[x]=tree[ls(x)]+tree[rs(x)];
}
void build(int id,int l,int r){
	tag[id]=0;
	if(l==r){
		tree[id]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(ls(id),l,mid);
	build(rs(id),mid+1,r);
	pushup(id);
}
void add(int id,int l,int r,int k){
	tag[id]+=k;
	tree[id]+=k*(r-l+1);
}
void push_down(int id,int l,int r){
	int mid=(l+r)/2;
	add(ls(id),l,mid,tag[id]);
	add(rs(id),mid+1,r,tag[id]);
	tag[id]=0;
}
void update(int nl,int nr,int l,int r,int id,int k){
	if(l>=nl&&r<=nr){
		tree[id]+=k*(r-l+1);
		tag[id]+=k;
		return;
	}
	push_down(id,l,r);
	int mid=(l+r)/2;
	if(nl<=mid)update(nl,nr,l,mid,ls(id),k);
	if(nr>mid)update(nl,nr,mid+1,r,rs(id),k);
	pushup(id);
}
int query(int nl,int nr,int l,int r,int id){
	int sum=0;
	if(l>=nl&&r<=nr)return tree[id];
	int mid=(l+r)/2;
	push_down(id,l,r);
	if(nl<=mid)sum+=query(nl,nr,l,mid,ls(id));
	if(nr>mid)sum+=query(nl,nr,mid+1,r,rs(id));
	return sum;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op;
		cin>>op;
		if(op==1){
			int l,r,k;
			cin>>l>>r>>k;
			update(l,r,1,n,1,k);
		}
		if(op==2){
			int l,r;
			cin>>l>>r;
			cout<<query(l,r,1,n,1)<<"\n";
		}
	}
	return 0;
}

另外,我每天都打一遍线段树有助于记忆吗?

2023/5/23 19:55
加载中...