题目链接

P6242 【模板】线段树 3

【模板】线段树 3

题目背景

本题是线段树维护区间最值操作与区间历史最值的模板。

题目描述

给出一个长度为 \(n\) 的数列 \(A\)，同时定义一个辅助数组 \(B\)，\(B\) 开始与 \(A\) 完全相同。接下来进行了 \(m\) 次操作，操作有五种类型，按以下格式给出：

• 1 l r k：对于所有的 \(i\in[l,r]\)，将 \(A_i\) 加上 \(k\)（\(k\) 可以为负数）。
• 2 l r v：对于所有的 \(i\in[l,r]\)，将 \(A_i\) 变成 \(\min(A_i,v)\)。
• 3 l r：求 \(\sum_{i=l}^{r}A_i\)。
• 4 l r：对于所有的 \(i\in[l,r]\)，求 \(A_i\) 的最大值。
• 5 l r：对于所有的 \(i\in[l,r]\)，求 \(B_i\) 的最大值。

在每一次操作后，我们都进行一次更新，让 \(B_i\gets\max(B_i,A_i)\)。

输入格式

第一行包含两个正整数 \(n,m\)，分别表示数列 \(A\) 的长度和操作次数。

第二行包含 \(n\) 个整数 \(A_1,A_2,\cdots,A_n\)，表示数列 \(A\)。

接下来 \(m\) 行，每行行首有一个整数 \(op\)，表示操作类型；接下来两个或三个整数表示操作参数，格式见【题目描述】。

输出格式

对于 \(op\in\{3,4,5\}\) 的操作，输出一行包含一个整数，表示这个询问的答案。

样例 #1

样例输入 #1

5 6
1 2 3 4 5
3 2 5
1 1 3 3
4 2 4
2 3 4 1
5 1 5
3 1 4

样例输出 #1

14
6
6
11

提示

样例说明 #1

数据规模与约定

• 对于测试点 \(1,2\)，满足 \(n,m\leq 5000\)；
• 对于测试点 \(3,4\)，满足 \(op\in\{1,2,3,4\}\)；
• 对于测试点 \(5,6\)，满足 \(op\in\{1,3,4,5\}\)；
• 对于全部测试数据，保证 \(1\leq n,m\leq 5\times 10^5\)，\(-5\times10^8\leq A_i\leq 5\times10^8\)，\(op\in[1,5]\)，\(1 \leq l\leq r \leq n\)，\(-2000\leq k\leq 2000\)，\(-5\times10^8\leq v\leq 5\times10^8\)。

提示

本题输入量较大，请使用合理高效的读入方法。

解题思路

吉司机线段树

难点主要在于区间取 min 和区间查询历史最值：
区间取 min 可将区间整个值分为最大值和非最大值部分，设置最大值 \(mxa\) 和其次数 \(cnt\) 以及次大值 \(lmxa\)，如果区间取 min 的值 \(v\) 范围为 \(lmxa<v<mxa\) 则可将最大值 \(mxa\) 更新为 \(v\)，如果当前区间的 \(mxa\leq v\) 则整个区间不用更新，否则如果 \(lmxa\leq v\) 的话递归到其子树上
对于区间查询历史最值，将区间分为最大值和非最大值后，设置 \(4\) 个懒标记：\(mxadd、nmxadd、mxmx、nmxmx\)，分别表示最大值、非最大值、最大值的最大值、非最大值的最大值的添加懒标记，后面两个懒标记主要用来处理历史最值问题，当 pushdown 时要判断左右子树的最大值是否为整个区间的最大值，所以要分为最大值和非最大值部分
另外一个难点在于 pushdown

• 时间复杂度：\(O(mlog^2)\)

代码

// Problem: P6242 【模板】线段树 3
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6242
// Memory Limit: 500 MB
// Time Limit: 3500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
// #define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=5e5+5,inf=0x3f3f3f3f;
int n,m,a[N];
struct Tr
{
	int l,r;
	int mxa,lmxa,mxb,cnt;
	int mxadd,nmxadd,mxmx,nmxmx;
	LL sum;
}tr[N<<2];
void pushup(int p)
{
	tr[p].mxa=max(tr[p<<1].mxa,tr[p<<1|1].mxa);
	tr[p].mxb=max(tr[p<<1].mxb,tr[p<<1|1].mxb);
	tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
	if(tr[p<<1].mxa==tr[p<<1|1].mxa)
		tr[p].lmxa=max(tr[p<<1].lmxa,tr[p<<1|1].lmxa),
		tr[p].cnt=tr[p<<1].cnt+tr[p<<1|1].cnt;
	else if(tr[p<<1].mxa>tr[p<<1|1].mxa)
		tr[p].lmxa=max(tr[p<<1].lmxa,tr[p<<1|1].mxa),
		tr[p].cnt=tr[p<<1].cnt;
	else
		tr[p].lmxa=max(tr[p<<1|1].lmxa,tr[p<<1].mxa),
		tr[p].cnt=tr[p<<1|1].cnt;
}
void change(int k1,int k2,int k3,int k4,int p)
{
	tr[p].sum+=1ll*k1*tr[p].cnt+1ll*k2*(tr[p].r-tr[p].l+1-tr[p].cnt);
	tr[p].mxb=max(tr[p].mxb,tr[p].mxa+k3);
	tr[p].mxa+=k1;
	if(tr[p].lmxa!=-inf)tr[p].lmxa+=k2;
	tr[p].mxmx=max(tr[p].mxmx,tr[p].mxadd+k3);
	tr[p].nmxmx=max(tr[p].nmxmx,tr[p].nmxadd+k4);
	tr[p].mxadd+=k1;
	tr[p].nmxadd+=k2;
}
void pushdown(int p)
{
	int mx=max(tr[p<<1].mxa,tr[p<<1|1].mxa);
	if(mx==tr[p<<1].mxa)
		change(tr[p].mxadd,tr[p].nmxadd,tr[p].mxmx,tr[p].nmxmx,p<<1);
	else
		change(tr[p].nmxadd,tr[p].nmxadd,tr[p].nmxmx,tr[p].nmxmx,p<<1);
	if(mx==tr[p<<1|1].mxa)
		change(tr[p].mxadd,tr[p].nmxadd,tr[p].mxmx,tr[p].nmxmx,p<<1|1);
	else
		change(tr[p].nmxadd,tr[p].nmxadd,tr[p].nmxmx,tr[p].nmxmx,p<<1|1);
	tr[p].mxadd=tr[p].nmxadd=tr[p].mxmx=tr[p].nmxmx=0;
}
void build(int p,int l,int r)
{
	tr[p]={l,r};
	if(l==r)
	{
		tr[p].sum=tr[p].mxa=tr[p].mxb=a[l];
		tr[p].cnt=1;
		tr[p].lmxa=-inf;
		return ;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	pushup(p);
}
void modify_add(int p,int l,int r,int k)
{
	if(l<=tr[p].l&&tr[p].r<=r)
	{
		tr[p].sum+=1ll*k*(tr[p].r-tr[p].l+1);
		tr[p].mxa+=k;
		tr[p].mxb=max(tr[p].mxb,tr[p].mxa);
		if(tr[p].lmxa!=-inf)tr[p].lmxa+=k;
		tr[p].mxadd+=k;
		tr[p].nmxadd+=k;
		tr[p].mxmx=max(tr[p].mxmx,tr[p].mxadd);
		tr[p].nmxmx=max(tr[p].nmxmx,tr[p].nmxadd);
		return ;
	}
	pushdown(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(l<=mid)
		modify_add(p<<1,l,r,k);
	if(r>mid)
		modify_add(p<<1|1,l,r,k);
	pushup(p);
}
void modify_min(int p,int l,int r,int v)
{
	if(tr[p].mxa<=v)return ;
	if(l<=tr[p].l&&tr[p].r<=r&&tr[p].lmxa<v)
	{
		int t=v-tr[p].mxa;
		tr[p].sum+=1ll*t*tr[p].cnt;
		tr[p].mxadd+=t;
		tr[p].mxa=v;	
		return ;
	}
	pushdown(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(l<=mid)
		modify_min(p<<1,l,r,v);
	if(r>mid)
		modify_min(p<<1|1,l,r,v);
	pushup(p);
}
LL ask_sum(int p,int l,int r)
{
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].sum;
	LL res=0;
	int mid=tr[p].l+tr[p].r>>1;
	pushdown(p);
	if(l<=mid)res+=ask_sum(p<<1,l,r);
	if(r>mid)res+=ask_sum(p<<1|1,l,r);
	return res;
}
int ask_maxa(int p,int l,int r)
{
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].mxa;
	int res=-inf;
	int mid=tr[p].l+tr[p].r>>1;
	pushdown(p);
	if(l<=mid)res=max(res,ask_maxa(p<<1,l,r));
	if(r>mid)res=max(res,ask_maxa(p<<1|1,l,r));
	return res;
}
int ask_maxb(int p,int l,int r)
{
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].mxb;
	int res=-inf;
	int mid=tr[p].l+tr[p].r>>1;
	pushdown(p);
	if(l<=mid)res=max(res,ask_maxb(p<<1,l,r));
	if(r>mid)res=max(res,ask_maxb(p<<1|1,l,r));
	return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,1,n);
    while(m--)
    {
    	int op,l,r,k,v;
    	scanf("%d%d%d",&op,&l,&r);
    	if(op==1)
    	{
    		scanf("%d",&k);
    		modify_add(1,l,r,k);
    	}
    	else if(op==2)
    	{
    		scanf("%d",&v);
    		modify_min(1,l,r,v);
    	}
    	else if(op==3)
    		printf("%lld\n",ask_sum(1,l,r));
    	else if(op==4)
    		printf("%d\n",ask_maxa(1,l,r));
    	else
    		printf("%d\n",ask_maxb(1,l,r));
    }
    return 0;
}