求助
查看原帖
求助
1040109
_Deer_Peach_楼主2024/9/24 22:32

好久没写线段树生疏了,不知道代码错哪里。

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int n,m,a[100001],tree[400001],tag[400001];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void push_up(int x){tree[x]=tree[ls(x)]+tree[rs(x)];}
void build(int x,int l,int r){
	if(l==r){tree[x]=a[l];return;}int mid=(l+r)>>1;
	build(ls(x),l,mid);build(rs(x),mid+1,r);push_up(x);
}inline void f(int x,int l,int r,int k){tag[x]+=k;tree[x]+=k*(r-l+1);}
inline void push_down(int x,int l,int r){int mid=(l+r)>>1;f(ls(x),l,mid,tag[x]);f(rs(x),mid+1,r,tag[x]);tag[x]=0;}
inline void update(int l,int r,int nowl,int nowr,int x,int k){
	if(nowl>=l&&nowr<=r){tree[x]+=k*(nowr-nowl+1);tag[x]+=k;return;}
	push_down(x,nowl,nowr);int mid=(nowl+nowr)>>1;
	if(l<=mid)update(l,r,nowl,mid,ls(x),k);
	if(r>mid)update(l,r,mid+1,nowr,rs(x),k);push_up(x);
}int query(int l,int r,int nowl,int nowr,int x){
	int res=0;if(nowl>=l&&nowr<=r)return tree[x];
	int mid=(l+r)>>1;push_down(x,nowl,nowr);if(l<=mid)res+=query(l,r,nowl,mid,ls(x));
	if(r>mid)res+=query(l,r,mid+1,nowr,rs(x));return res;
}
signed main(){
	IOS;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 x,y,k;cin>>x>>y>>k;update(x,y,1,n,1,k);}
		if(op==2){int x,y;cin>>x>>y;cout<<query(x,y,1,n,1)<<endl; }
	}return 0;
}
2024/9/24 22:32
加载中...