线段树板子90分求条
查看原帖
线段树板子90分求条
1283951
csxx601cjy楼主2025/2/7 23:21

最后2个点WA

我这种情况应该很特殊,翻遍讨论区也没用找到和我一样90分的,那位大佬看看是为什么。

#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;

struct segTree{
	struct node{
		int l,r;
		long long sum,tag=0;//l,r:管辖的范围;sum:区间和;tag:懒标记
	}t[4*MAXN];//4倍空间
	void pushup(int p){
		t[p].sum=t[p*2].sum+t[p*2+1].sum;
	}
	void pushdown(int p,int l,int r){//下传懒标记
		int mid=(l+r)/2;
		if(t[p].tag&&l<r){
			int lc=p*2,rc=lc+1;//左右孩子
			t[lc].sum+=t[p].tag*(mid-l+1);
			t[lc].tag+=t[p].tag;
			t[rc].sum+=t[p].tag*(r-mid);
			t[rc].tag+=t[p].tag;
			t[p].tag=0;
		}
	}
	void build(int a[],int p,int l,int r){//以p为根在l,r区间建树
		t[p].l=l,t[p].r=r;
		if(l==r){//叶子节点直接赋值
			t[p].sum=a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(a,p*2,l,mid);//左子树
		build(a,p*2+1,mid+1,r);//右子树
		pushup(p);
	}
	void upd(int p,int l,int r,int v,int L,int R){//给l,r区间的数加上v
		if(l<=L&&R<=r){//l,r包含区间p
			t[p].sum+=v*(R-L+1);
			t[p].tag+=v;
			return;
		}
		pushdown(p,L,R);
		int mid=(L+R)>>1;
		if(l<=mid)upd(p*2,l,r,v,L,mid);//左子树
		if(r>mid)upd(p*2+1,l,r,v,mid+1,R);//右子树
		pushup(p);
	}
	long long query(int p,int l,int r,int L,int R){//区间求和
		if(l<=L&&R<=r)return t[p].sum;//包含
		pushdown(p,L,R);
		int mid=(L+R)>>1;
		long long sum=0;
		if(l<=mid)sum+=query(p*2,l,r,L,mid);//左子树
		if(r>mid)sum+=query(p*2+1,l,r,mid+1,R);//右子树
		return sum;
	}
	void init(int a[],int n){build(a,1,1,n);}
	void add(int x,int y,int k){upd(1,x,y,k,t[1].l,t[1].r);}
	long long getsum(int x,int y){return query(1,x,y,t[1].l,t[1].r);}
};

segTree T;
int a[MAXN],n,m,op,x,y,k;
int main(){
	//freopen("P3372_19.in","r",stdin);
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	T.init(a,n);
	while(m--){
		cin>>op>>x>>y;
		if(op==1)cin>>k,T.add(x,y,k);
		if(op==2)cout<<T.getsum(x,y)<<'\n';
	}
	return 0;
}
2025/2/7 23:21
加载中...