为什么 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;
}