吉司机线段树

• $2025/02/13$

---

引入

【模板】线段树 3（区间最值操作、区间历史最值）

有 $5$ 个操作：

1 l r k，将区间 $[l,r]$ 中所有数加上 $k$；

2 l r v，将区间 $[l,r]$ 中 $>v$ 的数全部变为 $v$；

3 l r，求区间和；

4 l r，求区间最大值；

5 l r，求区间历史最大值。

---

Solution

最难处理的就是区间的 $a_i=min\{a_i,v\}$ 和历史最大值操作。

Code

#include<bits/stdc++.h>
#define int long long
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int inf=1e18;
const int N=5e5+10;
int n,m,a[N];
struct Tree {
	int sum,pmx;
	int mx1,cnt,mx2;
	int tag1,tag2;
	int tmx1,tmx2;
} tree[N<<2];
inline void push_up(int rt) {
	tree[rt].sum=tree[lson].sum+tree[rson].sum;
	tree[rt].pmx=max(tree[lson].pmx,tree[rson].pmx);
	if(tree[lson].mx1==tree[rson].mx1) {
		tree[rt].mx1=tree[lson].mx1;
		tree[rt].cnt=tree[lson].cnt+tree[rson].cnt;
		tree[rt].mx2=max(tree[lson].mx2,tree[rson].mx2);
	} else {
		if(tree[lson].mx1>tree[rson].mx1) {
			tree[rt].mx1=tree[lson].mx1;
			tree[rt].cnt=tree[lson].cnt;
			tree[rt].mx2=max(tree[lson].mx2,tree[rson].mx1);
		} else {
			tree[rt].mx1=tree[rson].mx1;
			tree[rt].cnt=tree[rson].cnt;
			tree[rt].mx2=max(tree[rson].mx2,tree[lson].mx1);
		}
	}
	return ;
}
inline void build(int rt,int l,int r) {
	if(l==r) {
		tree[rt].sum=tree[rt].mx1=tree[rt].pmx=a[l];
		tree[rt].mx2=-inf,tree[rt].cnt=1;
		return ;
	}
	int mid=(l+r)>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	push_up(rt);
	return ;
}
inline void modify(int rt,int l,int r,int tag1,int tag2,int tmx1,int tmx2) {
	tree[rt].sum+=tag1*tree[rt].cnt+tag2*(r-l+1-tree[rt].cnt);
	tree[rt].pmx=max(tree[rt].pmx,tree[rt].mx1+tmx1);
	tree[rt].mx1+=tag1;
	if(tag2!=-inf) tree[rt].mx2+=tag2;
	tree[rt].tmx1=max(tree[rt].tmx1,tree[rt].tag1+tmx1);
	tree[rt].tmx2=max(tree[rt].tmx2,tree[rt].tag2+tmx2);
	tree[rt].tag1+=tag1,tree[rt].tag2+=tag2;
	return ;
}
inline void push_down(int rt,int l,int r) {
	int mid=(l+r)>>1;
	int tag1=tree[rt].tag1,tag2=tree[rt].tag2;
	int tmx1=tree[rt].tmx1,tmx2=tree[rt].tmx2;
	int mx=max(tree[lson].mx1,tree[rson].mx1);
	if(tree[lson].mx1==mx)
		modify(lson,l,mid,tag1,tag2,tmx1,tmx2);
	else modify(lson,l,mid,tag2,tag2,tmx2,tmx2);
	if(tree[rson].mx1==mx)
		modify(rson,mid+1,r,tag1,tag2,tmx1,tmx2);
	else modify(rson,mid+1,r,tag2,tag2,tmx2,tmx2);
	tree[rt].tag1=tree[rt].tag2=tree[rt].tmx1=tree[rt].tmx2=0;
	return ;
}
inline void updateS(int rt,int l,int r,int s,int t,int k) {
	if(l>t||r<s)
		return ;
	if(s<=l&&r<=t) {
		modify(rt,l,r,k,k,k,k);
		return ;
	}
	push_down(rt,l,r);
	int mid=(l+r)>>1;
	updateS(lson,l,mid,s,t,k);
	updateS(rson,mid+1,r,s,t,k);
	push_up(rt);
	return ;
}
inline void updateM(int rt,int l,int r,int s,int t,int k) {
	if(l>t||r<s)
		return ;
	if(tree[rt].mx1<=k)
		return ;
	if(s<=l&&r<=t&&tree[rt].mx2<k) {
		int v=tree[rt].mx1-k;
		tree[rt].sum-=v*tree[rt].cnt;
		tree[rt].mx1=k,tree[rt].tag1-=v;
		return ;
	}
	push_down(rt,l,r);
	int mid=(l+r)>>1;
	updateM(lson,l,mid,s,t,k);
	updateM(rson,mid+1,r,s,t,k);
	push_up(rt);
	return ;
}
inline int queryS(int rt,int l,int r,int s,int t) {
	if(l>t||r<s)
		return 0;
	if(s<=l&&r<=t)
		return tree[rt].sum;
	push_down(rt,l,r);
	int mid=(l+r)>>1;
	return queryS(lson,l,mid,s,t)+queryS(rson,mid+1,r,s,t);
}
inline int queryM(int rt,int l,int r,int s,int t) {
	if(l>t||r<s)
		return -inf;
	if(s<=l&&r<=t)
		return tree[rt].mx1;
	push_down(rt,l,r);
	int mid=(l+r)>>1;
	return max(queryM(lson,l,mid,s,t),queryM(rson,mid+1,r,s,t));
}
inline int queryP(int rt,int l,int r,int s,int t) {
	if(l>t||r<s)
		return -inf;
	if(s<=l&&r<=t)
		return tree[rt].pmx;
	push_down(rt,l,r);
	int mid=(l+r)>>1;
	return max(queryP(lson,l,mid,s,t),queryP(rson,mid+1,r,s,t));
}
signed main() {
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	build(1,1,n);
	while(m--) {
		int op,l,r;
		scanf("%lld%lld%lld",&op,&l,&r);
		if(op==1) {
			int k;
			scanf("%lld",&k);
			updateS(1,1,n,l,r,k);
		}
		if(op==2) {
			int v;
			scanf("%lld",&v);
			updateM(1,1,n,l,r,v);
		}
		if(op==3)
			printf("%lld\n",queryS(1,1,n,l,r));
		if(op==4)
			printf("%lld\n",queryM(1,1,n,l,r));
		if(op==5)
			printf("%lld\n",queryP(1,1,n,l,r));
	}
	return 0;
}

---