刚学线段树,求条(玄关)
查看原帖
刚学线段树,求条(玄关)
1432246
_qumingnan_楼主2025/1/15 17:19

是操作 55 的问题

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e18;
int n,m;
struct node{int num,sum,ma,b,se;}t[2000005];
int add[2000005],Min[2000005];
inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;}
inline void push_up(int p){
	t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
	t[p].ma=max(t[ls(p)].ma,t[rs(p)].ma);
	t[p].b=max(t[p].b,t[p].ma);
	if(t[ls(p)].ma==t[rs(p)].ma){
		t[p].num=t[ls(p)].num+t[rs(p)].num;
		t[p].se=max(t[ls(p)].se,t[rs(p)].se);
	}
	else {
		t[p].se=max(t[ls(p)].se,max(t[rs(p)].se,min(t[ls(p)].ma,t[rs(p)].ma)));
		t[p].num=(t[ls(p)].ma>t[rs(p)].ma?t[ls(p)].num:t[rs(p)].num);
	}
}
inline void build(int p,int pl,int pr){
	if(pl==pr){
		cin>>t[p].sum;
		t[p].ma=t[p].sum;t[p].num=1,t[p].se=-INF;
		return ;
	}
	int mid=pl+pr>>1;
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
	push_up(p);
}
inline void mintag(int p,int pl,int pr,int X){
	Min[p]=X;
	t[p].sum=X*(pr-pl+1);
	t[p].ma=X;
	t[p].b=max(t[p].b,t[p].ma);
}
inline void addtag(int p,int pl,int pr,int X){
	add[p]+=X;
	t[p].sum+=X*(pr-pl+1);
	t[p].ma+=X;
	t[p].b=max(t[p].b,t[p].ma);
}
inline void push_down(int p,int pl,int pr){
	if(Min[p]!=INF){
		int mid=pl+pr>>1;
		mintag(ls(p),pl,mid,Min[p]);
		mintag(rs(p),mid+1,pr,Min[p]);
		Min[p]=INF;
	}
	if(add[p]){
		int mid=pl+pr>>1;
		addtag(ls(p),pl,mid,add[p]);
		addtag(rs(p),mid+1,pr,add[p]);
		add[p]=0;
	}
}
inline void updateadd(int L,int R,int p,int pl,int pr,int X){
	if(L<=pl&&pr<=R){addtag(p,pl,pr,X);return ;}
	push_down(p,pl,pr);
	int mid=pr+pl>>1;
	if(L<=mid)updateadd(L,R,ls(p),pl,mid,X);
	if(R>mid)updateadd(L,R,rs(p),mid+1,pr,X);
	push_up(p);
}
inline void updatemin(int L,int R,int p,int pl,int pr,int X){
	if(L<=pl&&pr<=R){mintag(p,pl,pr,X);return ;}
	push_down(p,pl,pr);
	int mid=pr+pl>>1;
	if(L<=mid)updatemin(L,R,ls(p),pl,mid,X);
	if(R>mid)updatemin(L,R,rs(p),mid+1,pr,X);
	push_up(p);
}
inline int querysum(int L,int R,int p,int pl,int pr){
	if(L<=pl&&pr<=R)return t[p].sum;
	push_down(p,pl,pr);
	int mid=pl+pr>>1,res=0;
	if(L<=mid)res+=querysum(L,R,ls(p),pl,mid);
	if(R>mid)res+=querysum(L,R,rs(p),mid+1,pr);
	return res;
} 
inline int querymax(int L,int R,int p,int pl,int pr){
	if(L<=pl&&pr<=R)return t[p].ma;
	push_down(p,pl,pr);
	int mid=pl+pr>>1,res=0;
	if(L<=mid)res=querymax(L,R,ls(p),pl,mid);
	if(R>mid)res=max(querymax(L,R,rs(p),mid+1,pr),res);
	return res;
}
inline int queryb(int L,int R,int p,int pl,int pr){
	if(L<=pl&&pr<=R)return t[p].b;
	push_down(p,pl,pr);
	int mid=pl+pr>>1,res=0;
	if(L<=mid)res=queryb(L,R,ls(p),pl,mid);
	if(R>mid)res=max(queryb(L,R,rs(p),mid+1,pr),res);
	return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	freopen("1.txt","r",stdin);
	freopen("1.out","w",stdout);
	cin>>n>>m;
	build(1,1,n);
	for(int i=1;i<=2000005;i++)Min[i]=INF;
	while(m--){
		int op,l,r,x;
		cin>>op>>l>>r;
		if(op==1)cin>>x,updateadd(l,r,1,1,n,x);
		if(op==2)cin>>x,updatemin(l,r,1,1,n,x);
		if(op==3)cout<<querysum(l,r,1,1,n)<<'\n';
		if(op==4)cout<<querymax(l,r,1,1,n)<<'\n';
		if(op==5)cout<<queryb(l,r,1,1,n)<<'\n';
	}
	return 0;
}
2025/1/15 17:19
加载中...