CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » legal_string » jxm2001 » 吉司机线段树
2020-2021:teams:legal_string:jxm2001:吉司机线段树

这是本文档旧的修订版！

目录

吉司机线段树

算法简介

一种支持区间最值修改及各种查询的线段树。

算法模板

模板一

HDU5306

题意

给定一个序列，支持下述三种操作：

  1. 对 $l\le i\le r$，$a_i=\min(a_i,v)$
  2. 询问区间 $[l,r]$ 的最大值
  3. 询问区间 $[l,r]$ 的和

题解

考虑建立线段树，维护区间最大值，区间最大值个数，区间次大值，区间和。

对修改操作，如果 $v$ 不小于区间最大值，则该操作没有意义，直接返回，否则先进行普通区间修改操作。

当普通区间修改操作遇到当前区间被包含于修改区间时，如果 $v$ 的大于区间次大值，则直接修改区间最大值，同时打上懒标记。

如果 $v$ 不大于区间次大值，则暴力修改子树。发现修改过程本质是 $\text{dfs}$，而 $\text{dfs}$ 时间复杂度等于遍历结点个数。

定义一个结点所代表区间的不同数值所构成的集合为该结点的数集，则暴力修改至少会合并该结点的最大值和次大值，于是该结点数集大小减小。

普通区间修改操作至多会使该结点的数集增加一个值，但普通区间修改的结点只有 $O(\log n)$ 个。

初始时所有结点的数集大小和为 $O(n\log n)$，于是修改操作的总复杂度为 $O((n+m)\log n)$。

对查询操作，和普通区间查询操作完全相同。

查看代码

查看代码 

const int MAXN=1e6+5;
int a[MAXN];
int lef[MAXN<<2],rig[MAXN<<2],maxv[MAXN<<2],maxc[MAXN<<2],secv[MAXN<<2],lazy[MAXN<<2];
LL sum[MAXN<<2];
void push_up(int k){
	sum[k]=sum[k<<1]+sum[k<<1|1];
	if(maxv[k<<1]==maxv[k<<1|1]){
		maxv[k]=maxv[k<<1];
		maxc[k]=maxc[k<<1]+maxc[k<<1|1];
		secv[k]=max(secv[k<<1],secv[k<<1|1]);
	}
	else if(maxv[k<<1]>maxv[k<<1|1]){
		maxv[k]=maxv[k<<1];
		maxc[k]=maxc[k<<1];
		secv[k]=max(secv[k<<1],maxv[k<<1|1]);
	}
	else{
		maxv[k]=maxv[k<<1|1];
		maxc[k]=maxc[k<<1|1];
		secv[k]=max(maxv[k<<1],secv[k<<1|1]);
	}
}
void push_tag(int k,int v){
	if(v>=maxv[k])return;
	sum[k]-=1LL*maxc[k]*(maxv[k]-v);
	maxv[k]=lazy[k]=v;
}
void push_down(int k){
	if(~lazy[k]){
		push_tag(k<<1,lazy[k]);
		push_tag(k<<1|1,lazy[k]);
		lazy[k]=-1;
	}
}
void build(int k,int L,int R){
	lef[k]=L,rig[k]=R,lazy[k]=-1;
	int M=L+R>>1;
	if(L==R){
		sum[k]=maxv[k]=a[M];
		secv[k]=-1;
		maxc[k]=1;
		return;
	}
	build(k<<1,L,M);
	build(k<<1|1,M+1,R);
	push_up(k);
}
void update(int k,int L,int R,int v){
	if(maxv[k]<=v)return;
	if(L<=lef[k]&&rig[k]<=R&&secv[k]<v)
	return push_tag(k,v);
	push_down(k);
	int mid=lef[k]+rig[k]>>1;
	if(mid>=L)update(k<<1,L,R,v);
	if(mid<R)update(k<<1|1,L,R,v);
	push_up(k);
}
int query_max(int k,int L,int R){
	if(L<=lef[k]&&rig[k]<=R)return maxv[k];
	push_down(k);
	int mid=lef[k]+rig[k]>>1,vl=-1,vr=-1;
	if(mid>=L)vl=query_max(k<<1,L,R);
	if(mid<R)vr=query_max(k<<1|1,L,R);
	return max(vl,vr);
}
LL query_sum(int k,int L,int R){
	if(L<=lef[k]&&rig[k]<=R)return sum[k];
	push_down(k);
	int mid=lef[k]+rig[k]>>1;
	LL s=0;
	if(mid>=L)s+=query_sum(k<<1,L,R);
	if(mid<R)s+=query_sum(k<<1|1,L,R);
	return s;
}
int main()
{
	int T=read_int();
	while(T--){
		int n=read_int(),q=read_int();
		_rep(i,1,n)a[i]=read_int();
		build(1,1,n);
		int opt,x,y;
		while(q--){
			opt=read_int(),x=read_int(),y=read_int();
			if(opt==0)
			update(1,x,y,read_int());
			else if(opt==1)
			enter(query_max(1,x,y));
			else
			enter(query_sum(1,x,y));
		}
	}
	return 0;
}

模板二

洛谷p6242

题意

给定一个序列，支持下述三种操作：

  1. 对 $l\le i\le r$，$a_i=a_i+v$
  2. 对 $l\le i\le r$，$a_i=\min(a_i,v)$
  3. 询问区间 $[l,r]$ 的和
  4. 询问区间 $[l,r]$ 的最大值
  5. 询问区间 $[l,r]$ 的历史最大值

题解

先只考虑操作 $1\sim 4$。对区间加操作，直接按普通区间加处理即可。但注意区间加会修改操作最值操作的懒标记，最大值和次大值。

另外区间加需要特判最值操作的懒标记和区间次大值不存在的情况。区间加操作本身的复杂度显然为 $O(\log n)$。

考虑区间加操作对区间最值操作的影响。对某个结点，不难发现该结点的数集大小增加的最大可能值等于区间加过程中遍历的该结点的子节点数。

一个结点在一次区间加过程中最多有 $O(\log n)$ 个子结点被遍历，而一次区间加过程最多遍历 $O(\log n)$ 个结点。

所以一次区间加操作最多使数集总和增加 $O(\log^2 n)$，所以总时间复杂度变为 $O(n\log n+m\log^2 n)$。

查看代码

查看代码 

const int MAXN=1e6+5,Inf=2e9;
int a[MAXN];
int lef[MAXN<<2],rig[MAXN<<2],maxv[MAXN<<2],maxc[MAXN<<2],secv[MAXN<<2];
int lazy1[MAXN<<2],lazy2[MAXN<<2];
LL sum[MAXN<<2];
void push_up(int k){
	sum[k]=sum[k<<1]+sum[k<<1|1];
	if(maxv[k<<1]==maxv[k<<1|1]){
		maxv[k]=maxv[k<<1];
		maxc[k]=maxc[k<<1]+maxc[k<<1|1];
		secv[k]=max(secv[k<<1],secv[k<<1|1]);
	}
	else if(maxv[k<<1]>maxv[k<<1|1]){
		maxv[k]=maxv[k<<1];
		maxc[k]=maxc[k<<1];
		secv[k]=max(secv[k<<1],maxv[k<<1|1]);
	}
	else{
		maxv[k]=maxv[k<<1|1];
		maxc[k]=maxc[k<<1|1];
		secv[k]=max(maxv[k<<1],secv[k<<1|1]);
	}
}
void push_add(int k,int v){
	sum[k]+=1LL*(rig[k]-lef[k]+1)*v;
	maxv[k]+=v,lazy1[k]+=v;
	if(secv[k]!=-Inf)secv[k]+=v;
	if(lazy2[k]!=-Inf)lazy2[k]+=v;
}
void push_min(int k,int v){
	if(v>=maxv[k])return;
	sum[k]-=1LL*maxc[k]*(maxv[k]-v);
	maxv[k]=lazy2[k]=v;
}
void push_down(int k){
	if(lazy1[k]){
		push_add(k<<1,lazy1[k]);
		push_add(k<<1|1,lazy1[k]);
		lazy1[k]=0;
	}
	if(lazy2[k]!=-Inf){
		push_min(k<<1,lazy2[k]);
		push_min(k<<1|1,lazy2[k]);
		lazy2[k]=-Inf;
	}
}
void build(int k,int L,int R){
	lef[k]=L,rig[k]=R,lazy1[k]=0,lazy2[k]=-Inf;
	int M=L+R>>1;
	if(L==R){
		sum[k]=maxv[k]=a[M];
		secv[k]=-Inf;
		maxc[k]=1;
		return;
	}
	build(k<<1,L,M);
	build(k<<1|1,M+1,R);
	push_up(k);
}
void update_add(int k,int L,int R,int v){
	if(L<=lef[k]&&rig[k]<=R)
	return push_add(k,v);
	push_down(k);
	int mid=lef[k]+rig[k]>>1;
	if(mid>=L)update_add(k<<1,L,R,v);
	if(mid<R)update_add(k<<1|1,L,R,v);
	push_up(k);
}
void update_min(int k,int L,int R,int v){
	if(maxv[k]<=v)return;
	if(L<=lef[k]&&rig[k]<=R&&secv[k]<v)
	return push_min(k,v);
	push_down(k);
	int mid=lef[k]+rig[k]>>1;
	if(mid>=L)update_min(k<<1,L,R,v);
	if(mid<R)update_min(k<<1|1,L,R,v);
	push_up(k);
}
LL query_sum(int k,int L,int R){
	if(L<=lef[k]&&rig[k]<=R)return sum[k];
	push_down(k);
	int mid=lef[k]+rig[k]>>1;
	LL s=0;
	if(mid>=L)s+=query_sum(k<<1,L,R);
	if(mid<R)s+=query_sum(k<<1|1,L,R);
	return s;
}
int query_max(int k,int L,int R){
	if(L<=lef[k]&&rig[k]<=R)return maxv[k];
	push_down(k);
	int mid=lef[k]+rig[k]>>1,vl=-Inf,vr=-Inf;
	if(mid>=L)vl=query_max(k<<1,L,R);
	if(mid<R)vr=query_max(k<<1|1,L,R);
	return max(vl,vr);
}
int main()
{
	int n=read_int(),q=read_int();
	_rep(i,1,n)a[i]=read_int();
	build(1,1,n);
	while(q--){
		int opt=read_int(),l=read_int(),r=read_int();
		switch(opt){
			case 1:
				update_add(1,l,r,read_int());
				break;
			case 2:
				update_min(1,l,r,read_int());
				break;
			case 3:
				enter(query_sum(1,l,r));
				break;
			case 4:
				enter(query_max(1,l,r));
				break;
		}
	}
	return 0;
}

接下来考虑操作 $1,3,4,5$。发现只需要维护加法懒标记的历史最大值即可维护区间历史最大值。

接下来考虑操作 $1\sim 5$。发现区间最值操作可以转化为对区间最值单独操作的特殊区间加法。

于是考虑对每个结点维护区间最值懒标记，区间最值的历史最值懒标记，区间非最值懒标记，区间非最值的历史最值懒标记。

总时间复杂度仍然为 $O(n\log n+m\log^2 n)$。

查看代码

查看代码 

const int MAXN=1e6+5,Inf=2e9;
int a[MAXN];
int lef[MAXN<<2],rig[MAXN<<2],maxv[MAXN<<2],mmaxv[MAXN<<2],maxc[MAXN<<2],secv[MAXN<<2];
int lazy1[MAXN<<2],lazy2[MAXN<<2],mlazy1[MAXN<<2],mlazy2[MAXN<<2];
LL sum[MAXN<<2];
void push_up(int k){
	sum[k]=sum[k<<1]+sum[k<<1|1];
	mmaxv[k]=max(mmaxv[k<<1],mmaxv[k<<1|1]);
	if(maxv[k<<1]==maxv[k<<1|1]){
		maxv[k]=maxv[k<<1];
		maxc[k]=maxc[k<<1]+maxc[k<<1|1];
		secv[k]=max(secv[k<<1],secv[k<<1|1]);
	}
	else if(maxv[k<<1]>maxv[k<<1|1]){
		maxv[k]=maxv[k<<1];
		maxc[k]=maxc[k<<1];
		secv[k]=max(secv[k<<1],maxv[k<<1|1]);
	}
	else{
		maxv[k]=maxv[k<<1|1];
		maxc[k]=maxc[k<<1|1];
		secv[k]=max(maxv[k<<1],secv[k<<1|1]);
	}
}
void push_tag(int k,int v1,int v2,int mv1,int mv2){
	sum[k]+=1LL*maxc[k]*v1+1LL*(rig[k]-lef[k]+1-maxc[k])*v2;
	mmaxv[k]=max(mmaxv[k],maxv[k]+mv1);
	mlazy1[k]=max(mlazy1[k],lazy1[k]+mv1);
	maxv[k]+=v1,lazy1[k]+=v1;
	mlazy2[k]=max(mlazy2[k],lazy2[k]+mv2);
	if(secv[k]!=-Inf)secv[k]+=v2;
	lazy2[k]+=v2;
}
void push_down(int k){
	int temp=max(maxv[k<<1],maxv[k<<1|1]);
	if(temp==maxv[k<<1])
	push_tag(k<<1,lazy1[k],lazy2[k],mlazy1[k],mlazy2[k]);
	else
	push_tag(k<<1,lazy2[k],lazy2[k],mlazy2[k],mlazy2[k]);
	if(temp==maxv[k<<1|1])
	push_tag(k<<1|1,lazy1[k],lazy2[k],mlazy1[k],mlazy2[k]);
	else
	push_tag(k<<1|1,lazy2[k],lazy2[k],mlazy2[k],mlazy2[k]);
	lazy1[k]=lazy2[k]=mlazy1[k]=mlazy2[k]=0;
}
void build(int k,int L,int R){
	lef[k]=L,rig[k]=R,lazy1[k]=lazy2[k]=mlazy1[k]=mlazy2[k]=0;
	int M=L+R>>1;
	if(L==R){
		sum[k]=maxv[k]=mmaxv[k]=a[M];
		secv[k]=-Inf;
		maxc[k]=1;
		return;
	}
	build(k<<1,L,M);
	build(k<<1|1,M+1,R);
	push_up(k);
}
void update_add(int k,int L,int R,int v){
	if(L<=lef[k]&&rig[k]<=R)
	return push_tag(k,v,v,v,v);
	push_down(k);
	int mid=lef[k]+rig[k]>>1;
	if(mid>=L)update_add(k<<1,L,R,v);
	if(mid<R)update_add(k<<1|1,L,R,v);
	push_up(k);
}
void update_min(int k,int L,int R,int v){
	if(maxv[k]<=v)return;
	if(L<=lef[k]&&rig[k]<=R&&secv[k]<v)
	return push_tag(k,v-maxv[k],0,v-maxv[k],0);
	push_down(k);
	int mid=lef[k]+rig[k]>>1;
	if(mid>=L)update_min(k<<1,L,R,v);
	if(mid<R)update_min(k<<1|1,L,R,v);
	push_up(k);
}
LL query_sum(int k,int L,int R){
	if(L<=lef[k]&&rig[k]<=R)return sum[k];
	push_down(k);
	int mid=lef[k]+rig[k]>>1;
	LL s=0;
	if(mid>=L)s+=query_sum(k<<1,L,R);
	if(mid<R)s+=query_sum(k<<1|1,L,R);
	return s;
}
int query_max(int k,int L,int R){
	if(L<=lef[k]&&rig[k]<=R)return maxv[k];
	push_down(k);
	int mid=lef[k]+rig[k]>>1,vl=-Inf,vr=-Inf;
	if(mid>=L)vl=query_max(k<<1,L,R);
	if(mid<R)vr=query_max(k<<1|1,L,R);
	return max(vl,vr);
}
int query_mmax(int k,int L,int R){
	if(L<=lef[k]&&rig[k]<=R)return mmaxv[k];
	push_down(k);
	int mid=lef[k]+rig[k]>>1,vl=-Inf,vr=-Inf;
	if(mid>=L)vl=query_mmax(k<<1,L,R);
	if(mid<R)vr=query_mmax(k<<1|1,L,R);
	return max(vl,vr);
}
int main()
{
	int n=read_int(),q=read_int();
	_rep(i,1,n)a[i]=read_int();
	build(1,1,n);
	while(q--){
		int opt=read_int(),l=read_int(),r=read_int();
		switch(opt){
			case 1:
				update_add(1,l,r,read_int());
				break;
			case 2:
				update_min(1,l,r,read_int());
				break;
			case 3:
				enter(query_sum(1,l,r));
				break;
			case 4:
				enter(query_max(1,l,r));
				break;
			case 5:
				enter(query_mmax(1,l,r));
				break;
		}
	}
	return 0;
}

算法例题

2020-2021/teams/legal_string/jxm2001/吉司机线段树.1601290388.txt.gz · 最后更改: 2020/09/28 18:53 由 jxm2001

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3