自动搬运

查看原文

来自洛谷，原作者为

	ran_qwq debug 深入思考 只靠样例与自己！

搬运于2025-08-24 22:59:51，当前版本为作者最后更新于2024-06-22 19:04:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

势能分析线段树模板题。

我们发现操作不是整个区间赋值为 $x$，而是对于小于/大于 $x$ 的数赋值为 $x$。常规的标记下传行不通，考虑“暴力”一点的做法：

线段树维护区间和 $sm$，区间最大值 $mx$，区间最小值 $mn$，区间次大值 $mxs$，区间次小值 $mns$。这里的次大次小都是严格的。

对于 $2$ 操作（取 max）的某个区间：

如果 $mn\ge k$，则操作到这里没有任何意义，直接 return。

如果 $mn<k<mns$，则下传懒标记后 return。更新 $sm$ 时要记录区间最大值个数 $mxc$ 和区间最小值个数 $mnc$，直接打懒标记。否则暴力递归。

$3$ 操作同理，把最小最大和符号反转一下即可。

合并信息时分讨一下；下传懒标记时要更新该区间的其他信息；注意下传懒标记的顺序。

这里着重讲一下时间复杂度证明。

定义势能为所有“最大值小于父节点最大值”的区间在线段树上的深度和。最小值类似，这里只分析最大值。

对于区间加：

如图，会对红色区间进行操作，顺带改变黄色区间的最大值。

而可能通过这次操作成为“最大值小于父节点最大值”的区间是如图的绿色区间。

这些绿色区间可以是操作区间（红色区间）的兄弟区间，每次的个数是 $\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)$。

证明参考了这篇题解，代码参考了 OI-wiki。

#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();
}