求助
查看原帖
求助
724648
light_searcher楼主2025/1/28 17:28

为什么 chkmx 和 chkmn 函数中的第一行不能取等号?取等号后 WA #4。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5,inf=1e18;
int n,q,a[N],mx[4*N],mx2[4*N],mn[4*N],mn2[4*N],sum[4*N],cmx[4*N],cmn[4*N],tmx[4*N],tmn[4*N],add[4*N];
void push_up(int x){
	sum[x]=sum[2*x]+sum[2*x+1];
	if(mx[2*x]==mx[2*x+1]){
		mx[x]=mx[2*x]; 
		cmx[x]=cmx[2*x]+cmx[2*x+1];
		mx2[x]=max(mx2[2*x],mx2[2*x+1]);
	} 
	else if(mx[2*x]>mx[2*x+1]){
		mx[x]=mx[2*x];
		cmx[x]=cmx[2*x];
		mx2[x]=max(mx2[2*x],mx[2*x+1]);
	}
	else{
		mx[x]=mx[2*x+1];
		cmx[x]=cmx[2*x+1];
		mx2[x]=max(mx[2*x],mx2[2*x+1]);
	}
	if(mn[2*x]==mn[2*x+1]){
		mn[x]=mn[2*x]; 
		cmn[x]=cmn[2*x]+cmn[2*x+1];
		mn2[x]=min(mn2[2*x],mn2[2*x+1]);
	} 
	else if(mn[2*x]<mn[2*x+1]){
		mn[x]=mn[2*x];
		cmn[x]=cmn[2*x];
		mn2[x]=min(mn2[2*x],mn[2*x+1]);
	}
	else{
		mn[x]=mn[2*x+1];
		cmn[x]=cmn[2*x+1];
		mn2[x]=min(mn[2*x],mn2[2*x+1]);
	}	
}
void build(int x,int l,int r){
	tmx[x]=-inf;
	tmn[x]=inf;
	if(l==r){
		sum[x]=mx[x]=mn[x]=a[l];
		mx2[x]=-inf;
		mn2[x]=inf;
		cmx[x]=cmn[x]=1;
		return; 
	}
	int mid=(l+r)/2;
	build(2*x,l,mid);
	build(2*x+1,mid+1,r);
	push_up(x);
}
void push_add(int x,int l,int r,int v){
	sum[x]+=(r-l+1)*v;
	mx[x]+=v;
	mn[x]+=v;
	if(mx2[x]!=-inf) mx2[x]+=v;
	if(mn2[x]!=inf) mn2[x]+=v;
	if(tmx[x]!=-inf) tmx[x]+=v;
	if(tmn[x]!=inf) tmn[x]+=v;
	add[x]+=v;
}
void push_mx(int x,int v){
	if(mn[x]>=v) return;
	sum[x]+=(v-mn[x])*cmn[x];
	if(mx2[x]==mn[x]) mx2[x]=v;
	if(mx[x]==mn[x]) mx[x]=v;
	if(tmn[x]<v) tmn[x]=v;
	mn[x]=v;
	tmx[x]=v;
}
void push_mn(int x,int v){
	if(mx[x]<=v) return;
	sum[x]-=(mx[x]-v)*cmx[x];
	if(mn2[x]==mx[x]) mn2[x]=v;
	if(mn[x]==mx[x]) mn[x]=v;
	if(tmx[x]>v) tmx[x]=v;
	mx[x]=v;
	tmn[x]=v;
}
void push_down(int x,int l,int r){
	if(add[x]){
		int mid=(l+r)/2;
		push_add(2*x,l,mid,add[x]);
		push_add(2*x+1,mid+1,r,add[x]);
		add[x]=0;
	}
	if(tmn[x]!=inf){
		push_mn(2*x,tmn[x]);
		push_mn(2*x+1,tmn[x]);
		tmn[x]=inf;
	}
	if(tmx[x]!=-inf){
		push_mx(2*x,tmx[x]);
		push_mx(2*x+1,tmx[x]);
		tmx[x]=-inf;
	}
}
void modify(int x,int l,int r,int L,int R,int v){
	if(l>=L&&r<=R) return push_add(x,l,r,v);
	push_down(x,l,r);
	int mid=(l+r)/2;
	if(L<=mid) modify(2*x,l,mid,L,R,v);
	if(R>mid) modify(2*x+1,mid+1,r,L,R,v);
	push_up(x);
}
void chkmx(int x,int l,int r,int L,int R,int v){
	if(l>=L&&r<=R&&mn2[x]>v) return push_mx(x,v);
	push_down(x,l,r);
	int mid=(l+r)/2;
	if(L<=mid) chkmx(2*x,l,mid,L,R,v);
	if(R>mid) chkmx(2*x+1,mid+1,r,L,R,v);
	push_up(x);
}
void chkmn(int x,int l,int r,int L,int R,int v){
	if(l>=L&&r<=R&&mx2[x]<v) return push_mn(x,v);
	push_down(x,l,r);
	int mid=(l+r)/2;
	if(L<=mid) chkmn(2*x,l,mid,L,R,v);
	if(R>mid) chkmn(2*x+1,mid+1,r,L,R,v);
	push_up(x);
}
int query(int x,int l,int r,int L,int R){
	if(l>=L&&r<=R) return mn[x]?0:cmn[x];
	push_down(x,l,r);
	int mid=(l+r)/2,ret=0;
	if(L<=mid) ret+=query(2*x,l,mid,L,R);
	if(R>mid) ret+=query(2*x+1,mid+1,r,L,R);
	return ret;
}
signed main(){
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	for(int opt,l,r,v;q;q--){
		scanf("%lld%lld%lld",&opt,&l,&r);
		if(opt==1){
			scanf("%lld",&v);
			chkmn(1,1,n,l,r,-1);
			chkmx(1,1,n,l,r,v);
		}
		else if(opt==2){
			scanf("%lld",&v);
			modify(1,1,n,l,r,v);
			chkmx(1,1,n,l,r,0);
		}
		else printf("%lld\n",query(1,1,n,l,r));
	}
	return 0;
}
2025/1/28 17:28
加载中...