$#C240215A. 线段树3

标签（Label）

• 线段树
• 模板

网址（Website）

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

题目（Problem）

题目背景

$\qquad$吉司机线段树。

题目描述

$\qquad$给出一个长度为 $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$ 的最大值。

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

输入格式

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

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

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

输出格式

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

样例

输入

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

输出

14
6
6
11

提示

样例说明

操作次数	输入内容	操作	数列	输出结果
0			$1,2,3,4,5$
1	3 2 5	求出 $[2,5]$ 所有数的和	$1,2,3,4,5$	14
2	1 1 3 3	将 $[1,3]$ 内所有数加 $3$	$4,5,6,4,5$
3	4 2 4	求出 $[2,4]$ 所有数的最大值	$4,5,6,4,5$	6
4	2 3 4 1	将 $[3,4]$ 所有数与 $1$ 取最小值	$4,5,1,1,5$
5	5 1 5	求出 $[1,5]$ 所有位置历史最大值的最大值	$4,5,1,1,5$	6
6	3 1 4	求出 $[1,4]$ 所有数的和	$4,5,1,1,5$	11

数据规模与约定

• 对于测试点 $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$。

提示

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

题解（Solution）

思路：

$\qquad$这道题是吉司机线段树的模板。

$\qquad$对于加法，直接修改即可。

$\qquad$对于取最小值，由于对区间更新最小值会影响到该区间的 $sum$ ，且不好判断，因此我们选择记录最大值及次大值，如果此时取最小值的 $v$ 满足在最大值和次大值之间，那么我们就只用修改最大值，并且更新 $sum$ 就好了。

$\qquad$考虑求 $b[i]$ 数组，由于记录的是历史的最大值，所以我们需要用一个值来记录 pushdown 下传的值和其下传的历史最大值。

$\qquad$一开始时，我构思的是通过修改 add 操作对 min 操作的影响来实现修改，但是最后发现在 pushdown 的时候会出现问题—— add 操作和 min 操作的先后会影响到 $hmax$ （即历史最大值）的值。（例如 add(1,n,5),min(1,n,2) 与 min(1,n,2),add(1,n,5) ，虽然对于 $sum$ 值的结果不会变（add 可以直接加在 to_min 上），但是这个先后顺序在进行 pushdown 时会被无视，导致历史值变大。

$\qquad$PS：没看懂的可以去 $hack$ 一下我 $50pts$ 的代码（在后面），找一下问题。

$\qquad$而正解是什么呢？我们可以直接把 min 操作，转换为单点修改当前区间的最大值（大概是这个意思），将加减操作分解为对当前的最大值的修改和对其余值的修改，那么当我们找到一个区间满足要取最小值的 $v$ 在其最大值与次大值之间时，就可以只对其最大值进行修改，而不会影响其他值。

总的来说：

需要这些变量：

• $sum$ ：当前区间的和
• $siz$ ：当前区间的个数（即 $r-l+1$ ）
• $mx1$ ：当前区间的最大值
• $mx2$：当前区间的次大值
• $cmx$：当前区间最大值的个数
• $hmx$：当前区间历史最大值
• $ad1$：最大值的加减懒标记
• $ad2$：除了最大值以外的值的加减懒标记
• $had1$：最大值的历史最大加减懒标记
• $had2$：除了最大值以外的值的历史最大加减懒标记

上传：

注意最大值的更新与最大值个数的记录：

void pushup(Tr &T,Tr L,Tr R){
	T.sum=L.sum+R.sum;
	T.mx1=max(L.mx1,R.mx1);
	if(L.mx1==R.mx1){
		T.mx2=max(L.mx2,R.mx2);
		T.cmx=L.cmx+R.cmx;
	}else{
		T.mx2=max(min(L.mx1,R.mx1),max(L.mx2,R.mx2));
		T.cmx=L.mx1>R.mx1?L.cmx:R.cmx;
	}T.hmx=max(L.hmx,R.hmx);
//	cerr<<"PUSHUP:"<<T.sum<<' '<<T.mx1<<' '<<T.mx2<<' '<<T.hmx<<'\n';
}

建树：

代码如下，正常建树就可以了：

#define mid (l+r>>1)
#define ls (p<<1)
#define rs (p<<1|1) 
struct Tr{
	int sum,siz,cmx;
	int mx1,mx2,hmx;
	int ad1,had1,ad2,had2;
}tr[N<<2|3];

void build(int p,int l,int r){
	tr[p]={a[l],r-l+1,1,a[l],-inf,a[l],0,0,0,0};
	if(l==r) return;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(tr[p],tr[ls],tr[rs]);
}

下传：

下传时先看修改：

void modify(int p,int k1,int hk1,int k2,int hk2){
	tr[p].sum += (tr[p].cmx * k1 + (tr[p].siz - tr[p].cmx)*k2);
	tr[p].hmx = max(tr[p].hmx, tr[p].mx1 + hk1);
	tr[p].mx1 += k1;
	
	if(tr[p].mx2!=-inf) tr[p].mx2+=k2;
	
	tr[p].had1 = max(tr[p].had1, tr[p].ad1 + hk1);
	tr[p].ad1 += k1;
	tr[p].had2 = max(tr[p].had2, tr[p].ad2 + hk2);
	tr[p].ad2 += k2;
}

pushdown 可以判断最大值在哪里，从而跟踪修改，如果这个区间不是最大值，那么直接下传其余值的标记，代码如下：

void pushdown(int p){
	int maxn = max(tr[ls].mx1, tr[rs].mx1);
	if(tr[ls].mx1 == maxn)
		modify(ls,tr[p].ad1,tr[p].had1,tr[p].ad2,tr[p].had2);
	else modify(ls,tr[p].ad2,tr[p].had2,tr[p].ad2,tr[p].had2);
	
	if(tr[rs].mx1 == maxn)
		modify(rs,tr[p].ad1,tr[p].had1,tr[p].ad2,tr[p].had2);
	else modify(rs,tr[p].ad2,tr[p].had2,tr[p].ad2,tr[p].had2);
		
	tr[p].ad1 = tr[p].had1 = tr[p].ad2 = tr[p].had2 = 0;
}

更新：

直接上代码：

void update_sum(int p,int l,int r,int L,int R,int k){
	if(L<=l && r<=R) return modify(p,k,k,k,k);
	pushdown(p);
    if(L<=mid) update_sum(ls,l,mid,L,R,k);
    if(R>mid) update_sum(rs,mid+1,r,L,R,k);
    pushup(tr[p],tr[ls],tr[rs]);
}

void update_min(int p,int l,int r,int L,int R,int v){
	if(tr[p].mx1<=v) return;
	if(L<=l && r<=R && tr[p].mx2<v)
		return modify(p,v-tr[p].mx1,v-tr[p].mx1,0,0);
	pushdown(p);
	if(L<=mid) update_min(ls,l,mid,L,R,v);
	if(R>mid) update_min(rs,mid+1,r,L,R,v);
	pushup(tr[p],tr[ls],tr[rs]);
}

询问：

这里直接一次搞定，可能需要理解一下这种打法：

Tr ask(int p,int l,int r,int L,int R){
	if(L<=l && r<=R) return tr[p];pushdown(p);
	if(R<=mid) return ask(ls,l,mid,L,R);
	if(L>mid) return ask(rs,mid+1,r,L,R);
	Tr T;return pushup(T,ask(ls,l,mid,L,mid),ask(rs,mid+1,r,mid+1,R)),T;
}

代码（Code）

50pts

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 501234;

int n,m,a[N];

#define mid (l+r>>1)
#define ls (p<<1)
#define rs (p<<1|1) 
struct Tr{
	int sum,siz;
	int mx1,mx2,cmx;
	int add,had,tmn;
	int hmx;
}tr[N<<2|3];

void pushup(Tr &T,Tr L,Tr R){
	T.sum=L.sum+R.sum;
	T.mx1=max(L.mx1,R.mx1);
	if(L.mx1==R.mx1){
		T.mx2=max(L.mx2,R.mx2);
		T.cmx=L.cmx+R.cmx;
	}else{
		T.mx2=max(min(L.mx1,R.mx1),max(L.mx2,R.mx2));
		T.cmx=L.mx1>R.mx1?L.cmx:R.cmx;
	}T.hmx=max(L.hmx,R.hmx);
}

void build(int p,int l,int r){
	tr[p]={a[l],r-l+1,a[l],-inf,1,0,0,inf,a[l]};
	if(l==r) return;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(tr[p],tr[ls],tr[rs]);
}

void push_add(int p,int k,int hk){
	tr[p].hmx=max(tr[p].hmx,tr[p].mx1+hk);
	tr[p].had=max(tr[p].had,tr[p].add+hk),
	
	tr[p].sum+=tr[p].siz*k;
	tr[p].mx1+=k,tr[p].mx2+=tr[p].mx2==-inf?0:k;
	tr[p].add+=k,tr[p].tmn+=tr[p].tmn==inf?0:k;
}

void push_min(int p,int v){
	if(tr[p].mx1 <= v) return;
	tr[p].sum+=(v-tr[p].mx1)*tr[p].cmx;
	tr[p].mx1=tr[p].tmn=v;
}

void pushdown(int p){
	if(tr[p].add || tr[p].had)
		push_add(ls,tr[p].add,tr[p].had),
		push_add(rs,tr[p].add,tr[p].had);
	if(tr[p].tmn!=inf)
		push_min(ls,tr[p].tmn);
		push_min(rs,tr[p].tmn);
	tr[p].add=tr[p].had=0;tr[p].tmn=inf;
}

void update_sum(int p,int l,int r,int L,int R,int k){
	if(L<=l && r<=R) return push_add(p,k,max(0ll,k));
	pushdown(p);
    if(L<=mid) update_sum(ls,l,mid,L,R,k);
    if(R>mid) update_sum(rs,mid+1,r,L,R,k);
    pushup(tr[p],tr[ls],tr[rs]);
}

void update_min(int p,int l,int r,int L,int R,int v){
	if(tr[p].mx1<=v) return;
	if(L<=l && r<=R && tr[p].mx2<v) return push_min(p,v);
	pushdown(p);
	if(L<=mid) update_min(ls,l,mid,L,R,v);
	if(R>mid) update_min(rs,mid+1,r,L,R,v);
	pushup(tr[p],tr[ls],tr[rs]);
}

Tr ask(int p,int l,int r,int L,int R){
	if(L<=l && r<=R) return tr[p];pushdown(p);
	if(R<=mid) return ask(ls,l,mid,L,R);
	if(L>mid) return ask(rs,mid+1,r,L,R);
	Tr T;return pushup(T,ask(ls,l,mid,L,mid),ask(rs,mid+1,r,mid+1,R)),T;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;For(i,1,n) a[i]=input();
	int Tim=clock();build(1,1,n);
	while(m--){
		int opt=input(),l=input(),r=input(),k;
		if(opt==1) update_sum(1,1,n,l,r,k=input());
		if(opt==2) update_min(1,1,n,l,r,k=input());
		if(opt==3) cout<<ask(1,1,n,l,r).sum<<'\n';
		if(opt==4) cout<<ask(1,1,n,l,r).mx1<<'\n';
		if(opt==5) cout<<ask(1,1,n,l,r).hmx<<'\n';
	}return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}

100pts

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 501234;

int n,m,a[N];

#define mid (l+r>>1)
#define ls (p<<1)
#define rs (p<<1|1) 
struct Tr{
	int sum,siz,cmx;
	int mx1,mx2,hmx;
	int ad1,had1,ad2,had2;
}tr[N<<2|3];

void pushup(Tr &T,Tr L,Tr R){
	T.sum=L.sum+R.sum;
	T.mx1=max(L.mx1,R.mx1);
	if(L.mx1==R.mx1){
		T.mx2=max(L.mx2,R.mx2);
		T.cmx=L.cmx+R.cmx;
	}else{
		T.mx2=max(min(L.mx1,R.mx1),max(L.mx2,R.mx2));
		T.cmx=L.mx1>R.mx1?L.cmx:R.cmx;
	}T.hmx=max(L.hmx,R.hmx);
}

void build(int p,int l,int r){
	tr[p]={a[l],r-l+1,1,a[l],-inf,a[l],0,0,0,0};
	if(l==r) return;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(tr[p],tr[ls],tr[rs]);
}

void modify(int p,int k1,int hk1,int k2,int hk2){
	tr[p].sum += (tr[p].cmx * k1 + (tr[p].siz - tr[p].cmx)*k2);
	tr[p].hmx = max(tr[p].hmx, tr[p].mx1 + hk1);
	tr[p].mx1 += k1;
	
	if(tr[p].mx2!=-inf) tr[p].mx2+=k2;
	
	tr[p].had1 = max(tr[p].had1, tr[p].ad1 + hk1);
	tr[p].ad1 += k1;
	tr[p].had2 = max(tr[p].had2, tr[p].ad2 + hk2);
	tr[p].ad2 += k2;
}

void pushdown(int p){
	int maxn = max(tr[ls].mx1, tr[rs].mx1);
	if(tr[ls].mx1 == maxn)
		modify(ls,tr[p].ad1,tr[p].had1,tr[p].ad2,tr[p].had2);
	else modify(ls,tr[p].ad2,tr[p].had2,tr[p].ad2,tr[p].had2);
	
	if(tr[rs].mx1 == maxn)
		modify(rs,tr[p].ad1,tr[p].had1,tr[p].ad2,tr[p].had2);
	else modify(rs,tr[p].ad2,tr[p].had2,tr[p].ad2,tr[p].had2);
		
	tr[p].ad1 = tr[p].had1 = tr[p].ad2 = tr[p].had2 = 0;
}

void update_sum(int p,int l,int r,int L,int R,int k){
	if(L<=l && r<=R) return modify(p,k,k,k,k);
	pushdown(p);
    if(L<=mid) update_sum(ls,l,mid,L,R,k);
    if(R>mid) update_sum(rs,mid+1,r,L,R,k);
    pushup(tr[p],tr[ls],tr[rs]);
}

void update_min(int p,int l,int r,int L,int R,int v){
	if(tr[p].mx1<=v) return;
	if(L<=l && r<=R && tr[p].mx2<v)
		return modify(p,v-tr[p].mx1,v-tr[p].mx1,0,0);
	pushdown(p);
	if(L<=mid) update_min(ls,l,mid,L,R,v);
	if(R>mid) update_min(rs,mid+1,r,L,R,v);
	pushup(tr[p],tr[ls],tr[rs]);
}

Tr ask(int p,int l,int r,int L,int R){
	if(L<=l && r<=R) return tr[p];pushdown(p);
	if(R<=mid) return ask(ls,l,mid,L,R);
	if(L>mid) return ask(rs,mid+1,r,L,R);
	Tr T;return pushup(T,ask(ls,l,mid,L,mid),ask(rs,mid+1,r,mid+1,R)),T;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;For(i,1,n) a[i]=input();
	int Tim=clock();build(1,1,n);
	while(m--){
		int opt=input(),l=input(),r=input(),k;
		if(opt==1) update_sum(1,1,n,l,r,k=input());
		if(opt==2) update_min(1,1,n,l,r,k=input());
		if(opt==3) cout<<ask(1,1,n,l,r).sum<<'\n';
		if(opt==4) cout<<ask(1,1,n,l,r).mx1<<'\n';
		if(opt==5) cout<<ask(1,1,n,l,r).hmx<<'\n';
	}return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}