#C240215A. 线段树3

线段树
题目
发布日期:   2024-02-15
更新日期:   2024-02-15
文章字数:   3.2k
阅读时长:   16 分

#C240215A. 线段树3

前言（Front talk)

时隔数月，终于打出来了！

网址（Website）

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

题目（Problem）

题目背景

吉司机线段树。

题目描述

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

  • 1 l r k：对于所有的，将加上（可以为负数）。
  • 2 l r v：对于所有的，将变成。
  • 3 l r：求。
  • 4 l r：对于所有的，求的最大值。
  • 5 l r：对于所有的，求的最大值。

在每一次操作后，我们都进行一次更新，让。

输入格式

第一行包含两个正整数，分别表示数列的长度和操作次数。

第二行包含个整数，表示数列。

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

输出格式

对于的操作，输出一行包含一个整数，表示这个询问的答案。

样例

输入

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
13 2 5求出所有数的和14
21 1 3 3将内所有数加
34 2 4求出所有数的最大值6
42 3 4 1将所有数与取最小值
55 1 5求出所有位置历史最大值的最大值6
63 1 4求出所有数的和11

数据规模与约定

  • 对于测试点，满足；
  • 对于测试点，满足；
  • 对于测试点，满足；
  • 对于全部测试数据，保证，，，，，。

提示

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

题解（Solution）

思路：

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

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

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

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

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

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

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

总的来说：

需要这些变量：

  • ：当前区间的和
  • ：当前区间的个数（即）
  • ：当前区间的最大值
  • ：当前区间的次大值
  • ：当前区间最大值的个数
  • ：当前区间历史最大值
  • ：最大值的加减懒标记
  • ：除了最大值以外的值的加减懒标记
  • ：最大值的历史最大加减懒标记
  • ：除了最大值以外的值的历史最大加减懒标记

上传：

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

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;
}
文章作者: WolfDeer
文章链接: https://wolfdeer62456.github.io/projecthttps://wolfdeer62456.github.io/2024/02/15/c240215a-xian-duan-shu-3/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 WolfDeer !
线段树
赏
  目录