RE一个点,线段树求助(简单的线段树)
查看原帖
RE一个点,线段树求助(简单的线段树)
565945
Azure__楼主2022/4/23 21:11

帮帮孩子吧,最后一个点RE

#include<bits/stdc++.h>
#define int long long
#define num -1145141919810
using namespace std;
int n,q;
struct node{
	int l,r,w,sum,cover;
} tree[4*1000000+1];
inline int read(){
	char c; int x=0,f=1; c=getchar();
	while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); }
	while(c>='0'&&c<='9'){ x=(x<<3)+(x<<1)+(c^48); c=getchar(); }
	return x*f;
}
inline void push_up(int k){
	tree[k].w=max(tree[k<<1].w,tree[k<<1|1].w);
}
inline void build(int l,int r,int k){
	tree[k].l=l; tree[k].r=r;
	tree[k].sum=0; tree[k].cover=num;
	if(l==r){
		tree[k].w=read();
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,k<<1); build(mid+1,r,k<<1|1);
	push_up(k);
}
inline void push_downcover(int k){
	tree[k<<1].w=tree[k].cover;
	tree[k<<1|1].w=tree[k].cover;
	tree[k<<1].cover=tree[k].cover;
	tree[k<<1|1].cover=tree[k].cover;
	tree[k<<1].sum=0;
	tree[k<<1|1].sum=0;
	tree[k].cover=num;
}
inline void push_downsum(int k){
	if(tree[k].cover!=num) push_downcover(k);
	tree[k<<1].w+=tree[k].sum;
	tree[k<<1|1].w+=tree[k].sum;
	tree[k<<1].sum+=tree[k].sum;
	tree[k<<1|1].sum+=tree[k].sum;
	tree[k].sum=0;
}
inline int ask_interval(int k,int a,int b){
	if(tree[k].l>=a&&tree[k].r<=b){
		return tree[k].w;
	}
	if(tree[k].cover!=num) push_downcover(k);
	if(tree[k].sum) push_downsum(k);
	int mid=(tree[k].l+tree[k].r)>>1,ans=LLONG_MIN;
	if(a<=mid) ans=max(ans,ask_interval(k<<1,a,b));
	if(b>mid) ans=max(ans,ask_interval(k<<1|1,a,b));
	return ans;
}
inline void change_interval(int k,int a,int b,int y){
	if(tree[k].l>=a&&tree[k].r<=b){
		if(tree[k].cover!=num) push_downcover(k);
		tree[k].w+=y;
		tree[k].sum+=y;
		return;
	}
	if(tree[k].cover!=num) push_downcover(k);
	if(tree[k].sum) push_downsum(k);
	int mid=(tree[k].l+tree[k].r)>>1;
	if(a<=mid) change_interval(k<<1,a,b,y);
	if(b>mid) change_interval(k<<1|1,a,b,y);
	push_up(k);
}
inline void change_interval2(int k,int a,int b,int y){
	if(tree[k].l>=a&&tree[k].r<=b){
		tree[k].w=y;
		tree[k].cover=y;
		tree[k].sum=0;
		return;
	}
	if(tree[k].cover!=num) push_downcover(k);
	if(tree[k].sum) push_downsum(k);
	int mid=(tree[k].l+tree[k].r)>>1;
	if(a<=mid) change_interval2(k<<1,a,b,y);
	if(b>mid) change_interval2(k<<1|1,a,b,y);
	push_up(k);
}
signed main()
{
	n=read();
	q=read();
	build(1,n,1);
	while(q--){
		int opt=read();
		if(opt==1){
			int a=read(),b=read(),y=read();
			change_interval2(1,a,b,y);
		}
		if(opt==2){
			int a=read(),b=read(),y=read();
			change_interval(1,a,b,y);
		}
		if(opt==3){
			int a=read(),b=read();
			printf("%lld\n",ask_interval(1,a,b));
		}
	}
	return 0;
}
```cpp
2022/4/23 21:11
加载中...