题解：P10639 BZOJ4695 最佳女选手
ran_qwq
·
·
题解
势能分析线段树模板题。
我们发现操作不是整个区间赋值为 x，而是对于小于/大于 x 的数赋值为 x。常规的标记下传行不通，考虑“暴力”一点的做法：
线段树维护区间和 sm，区间最大值 mx，区间最小值 mn，区间次大值 mxs，区间次小值 mns。这里的次大次小都是严格的。
对于 2 操作（取 max）的某个区间：
如果 mn\ge k，则操作到这里没有任何意义，直接 return。
如果 mn<k<mns，则下传懒标记后 return。更新 sm 时要记录区间最大值个数 mxc 和区间最小值个数 mnc，直接打懒标记。否则暴力递归。
合并信息时分讨一下；下传懒标记时要更新该区间的其他信息；注意下传懒标记的顺序。
---
这里着重讲一下时间复杂度证明。
定义势能为所有“最大值小于父节点最大值”的区间在线段树上的深度和。最小值类似，这里只分析最大值。
对于区间加：
如图，会对红色区间进行操作，顺带改变黄色区间的最大值。
而可能通过这次操作成为“最大值小于父节点最大值”的区间是如图的绿色区间。
这些绿色区间可以是操作区间（红色区间）的兄弟区间，每次的个数是 $\log n$ 级别的。所以每次区间加新增势能最多 $\log^2n$。
对于取最小值，若对一个父区间，只递归左子区间，则只能使左子区间最大值越来越接近父区间最大值，不会对势能产生正贡献。
定义一个区间的权值为该区间内 $\le x$ 的数。由此显然得出，取最小值过程必然将原区间划分为若干个权值为 $1$ 的小区间，然后不能划分，打懒标记。
最末端划分的区间必然满足以下性质：父区间次大值 $\ge x$，两个子区间次大值均 $<x$。所以父亲的最、次大值分别是两子区间的最大值。
且操作前父亲的次大值对应的子区间有势能，另一个子区间无势能。操作后父亲及两个子区间最大值均为 $x$，对势能有深度的负贡献。
即均摊下来，每访问一个区间就对势能有 $-1$ 的贡献。
需要注意的是取最大值的过程是对 min 的势能有负贡献，所以 min 的势能同理。
综上所述，min 和 max 的势能在任意时刻均是 $n\log^2n$ 级别，所以取最小值和取最大值操作的访问区间次数也是 $n\log^2n$ 级别。
即总时间复杂度 $O(n\log^2n)$。
证明参考了[这篇题解](https://blog.51cto.com/u_15064643/4123186)，代码参考了 OI-wiki。
```cpp
#include<bits/stdc++.h>
#define il inline
#define ui unsigned int
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define ldb long double
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define fir first
#define sec second
#define gc getchar
#define pc putchar
#define mst(a,x) memset(a,x,sizeof a)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pct __builtin_popcount
using namespace std;
const int N=5e5+10,INF=0x3f3f3f3f,MOD=1e9+7;
const ll INFll=0x3f3f3f3f3f3f3f3f;
il int rd() {int x=0,f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il ll rdll() {ll x=0; int f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il void wr(int x) {if(x<-2147483647) {printf("-2147483648"); return;} if(x<0) {pc('-'),wr(-x); return;} if(x<10) {pc(x+'0'); return;} wr(x/10),pc(x%10+'0');}
il void wrll(ll x) {if(x<-9223372036854775807) return (void)printf("-9223372036854775808"); if(x<0) return pc('-'),wrll(-x); if(x<10) return (void)pc(x+'0'); wrll(x/10),pc(x%10+'0');}
il void wr(int x,char *s) {wr(x),printf("%s",s);}
il void wrll(ll x,char *s) {wrll(x),printf("%s",s);}
il int vmod(int x) {return x>=MOD?x-MOD:x;}
il int vadd(int x,int y) {return vmod(x+y);}
il int vsub(int x,int y) {return vmod(x-y+MOD);}
il int vmul(int x,int y) {return 1ll*x*y%MOD;}
int n,m,a[N];
struct SGT {
#define ls (id<<1)
#define rs (id<<1|1)
#define mid (l+r>>1)
#define smt(id) tr[id].smt
#define mx(id) tr[id].mx
#define mxc(id) tr[id].mxc
#define mxs(id) tr[id].mxs
#define mxt(id) tr[id].mxt
#define mn(id) tr[id].mn
#define mnc(id) tr[id].mnc
#define mns(id) tr[id].mns
#define mnt(id) tr[id].mnt
#define sm(id) tr[id].sm
struct nd {int smt,mx,mxc,mxs,mxt,mn,mnc,mns,mnt; ll sm;} tr[N<<2];
void pu(int id) {
sm(id)=sm(ls)+sm(rs);
if(mx(ls)>mx(rs)) mx(id)=mx(ls),mxc(id)=mxc(ls),mxs(id)=max(mxs(ls),mx(rs));
else if(mx(ls)<mx(rs)) mx(id)=mx(rs),mxc(id)=mxc(rs),mxs(id)=max(mx(ls),mxs(rs));
else mx(id)=mx(ls),mxc(id)=mxc(ls)+mxc(rs),mxs(id)=max(mxs(ls),mxs(rs));
if(mn(ls)<mn(rs)) mn(id)=mn(ls),mnc(id)=mnc(ls),mns(id)=min(mns(ls),mn(rs));
else if(mn(ls)>mn(rs)) mn(id)=mn(rs),mnc(id)=mnc(rs),mns(id)=min(mn(ls),mns(rs));
else mn(id)=mn(ls),mnc(id)=mnc(ls)+mnc(rs),mns(id)=min(mns(ls),mns(rs));
}
void ad(int &x,int k) {x!=INF&&x!=-INF&&(x+=k);}
void apd(int id,int len,int k) {sm(id)+=1ll*len*k,ad(mx(id),k),ad(mxs(id),k),ad(mxt(id),k),ad(mn(id),k),ad(mns(id),k),ad(mnt(id),k),ad(smt(id),k);}
void mxpd(int id,int k) {
if(mn(id)>k) return; sm(id)+=1ll*(k-mn(id))*mnc(id),mxt(id)=k;
if(mn(id)==mx(id)) mx(id)=k; if(mn(id)==mxs(id)) mxs(id)=k; mnt(id)=max(mnt(id),k),mn(id)=k;
}
void mnpd(int id,int k) {
if(mx(id)<k) return; sm(id)+=1ll*(k-mx(id))*mxc(id),mnt(id)=k;
if(mx(id)==mn(id)) mn(id)=k; if(mx(id)==mns(id)) mns(id)=k; mxt(id)=min(mxt(id),k),mx(id)=k;
}
void pd(int id,int l,int r) {
if(smt(id)) apd(ls,mid-l+1,smt(id)),apd(rs,r-mid,smt(id)); if(mxt(id)!=-INF) mxpd(ls,mxt(id)),mxpd(rs,mxt(id)); if(mnt(id)!=INF) mnpd(ls,mnt(id)),mnpd(rs,mnt(id));
smt(id)=0,mxt(id)=-INF,mnt(id)=INF;
}
void bld(int id,int l,int r) {
if(l==r) return tr[id]={0,a[l],1,-INF,-INF,a[l],1,INF,INF,a[l]},void();
bld(ls,l,mid),bld(rs,mid+1,r),pu(id),mxt(id)=-INF,mnt(id)=INF;
}
void aupd(int id,int l,int r,int L,int R,int k) {
if(L<=l&&r<=R) return apd(id,r-l+1,k);
pd(id,l,r),L<=mid?aupd(ls,l,mid,L,R,k):void(),R>mid?aupd(rs,mid+1,r,L,R,k):void(),pu(id);
}
void mxupd(int id,int l,int r,int L,int R,int k) {
if(mn(id)>=k) return; if(L<=l&&r<=R&&mns(id)>k) return mxpd(id,k); if(l==r) return;
pd(id,l,r),L<=mid?mxupd(ls,l,mid,L,R,k):void(),R>mid?mxupd(rs,mid+1,r,L,R,k):void(),pu(id);
}
void mnupd(int id,int l,int r,int L,int R,int k) {
if(mx(id)<=k) return; if(L<=l&&r<=R&&mxs(id)<k) return mnpd(id,k); if(l==r) return;
pd(id,l,r),L<=mid?mnupd(ls,l,mid,L,R,k):void(),R>mid?mnupd(rs,mid+1,r,L,R,k):void(),pu(id);
}
ll sqry(int id,int l,int r,int L,int R) {
if(L<=l&&r<=R) return sm(id);
pd(id,l,r); return (L<=mid?sqry(ls,l,mid,L,R):0)+(R>mid?sqry(rs,mid+1,r,L,R):0);
}
int mxqry(int id,int l,int r,int L,int R) {
if(L<=l&&r<=R) return mx(id);
pd(id,l,r); return max(L<=mid?mxqry(ls,l,mid,L,R):-INF,R>mid?mxqry(rs,mid+1,r,L,R):-INF);
}
int mnqry(int id,int l,int r,int L,int R) {
if(L<=l&&r<=R) return mn(id);
pd(id,l,r); return min(L<=mid?mnqry(ls,l,mid,L,R):INF,R>mid?mnqry(rs,mid+1,r,L,R):INF);
}
}T;
void QwQ() {
n=rd(); for(int i=1;i<=n;i++) a[i]=rd(); m=rd(),T.bld(1,1,n);
for(int op,l,r;m--;) {
op=rd(),l=rd(),r=rd();
if(op==1) T.aupd(1,1,n,l,r,rd()); else if(op==2) T.mxupd(1,1,n,l,r,rd()); else if(op==3) T.mnupd(1,1,n,l,r,rd());
else if(op==4) wrll(T.sqry(1,1,n,l,r),"\n"); else if(op==5) wr(T.mxqry(1,1,n,l,r),"\n"); else wr(T.mnqry(1,1,n,l,r),"\n");
}
}
signed main() {
int T=1; while(T--) QwQ();
}
```