线段树板子全RE求调,目测数组大小无误
查看原帖
线段树板子全RE求调,目测数组大小无误
422348
Yang818楼主2023/10/20 19:13
#include<bits/stdc++.h>
#define F(_b,_e) for(int i=_b;i<=_e;i++)
#define int long long
using namespace std;

inline int read(){
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f*x;
}
void write(int x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
const int MAXN=2e5+5;
struct Seg_tree{
	int l,r;
	long long val,tag;
}t[MAXN<<2];
int a[MAXN],n,m; 

void build(int pos,int left,int right){
	t[pos].l=left;
	t[pos].r=right;
	if(left==right){
		t[pos].val=a[left];
		return;
	}
	int mid=(left+right)/2;
	build(pos*2,left,mid);
	build(pos*2+1,mid+1,right);
}

void spread_down(int pos){
	t[pos*2].tag=t[pos].tag;
	t[pos*2+1].tag=t[pos].tag;
	t[pos*2].val+=(t[pos*2].r-t[pos*2+1].l+1)*t[pos].tag;
	t[pos*2+1].val+=(t[pos*2+1].r-t[pos*2+1].l+1)*t[pos].tag;
	t[pos].tag=0;
} 

void modify(int pos,int left,int right,int delta){
	if(t[pos].l>=left && t[pos].r<=right){
		t[pos].val+=delta*(t[pos].r-t[pos].l+1);
		t[pos].tag+=delta;
		return;
	}
	int mid=(t[pos].l+t[pos].r)/2;
	if(left<=mid)	modify(pos*2,left,right,delta);
	if(right>mid)	modify(pos*2+1,left,right,delta);
	t[pos].val=t[pos*2].val+t[pos*2+1].val;
	return;
} 

int query(int pos,int left,int right){
	long long ans=0;
	if(t[pos].l>=left&&t[pos].r<=right)
		return t[pos].val;
	int mid=(t[pos].l+t[pos].r)/2;
	if(left<=mid)
		ans+=query(pos*2,left,right);
	if(right>mid)
		ans+=query(pos*2+1,left,right);
	return ans;
}

signed main(){
	//ios::sync_with_stdio(0);
	n=read();
	m=read();
	while(m--){
		int op=read();
		if(op==1){
			int l=read();
			int r=read();
			int d=read();
			modify(1,l,r,d);
		}
		if(op==2){
			int l=read();
			int r=read();
			cout<<query(1,l,r)<<endl;
		}
	}
	return 0;
}

2023/10/20 19:13
加载中...