首页 > 其他分享 >吉司机线段树

吉司机线段树

时间：2024-07-15 09:29:56浏览次数：6  
标签：lzy int 线段 tr mx 司机 st 最大值

吉司机线段树

为了方便说板子，这里直接把板子题放上去讲了。

线段树 3

简单说一下 \(5\) 个操作都在干什么：

  • 区间加一个数。

  • 区间和一个数取最小值。

  • 区间求和。

  • 区间求最大值。

  • 区间求历史最大值。

好了，前 \(4\) 个操作如果单独拉出来出成一道题，显然是好做的，于是我们的难点就是最后一个操作。

因此，我们的线段树要维护很多东西：区间左右端点，区间和，最大值，严格次大值等，具体注释放在下面代码里了，因为实在太多了：

struct node{
	int l,r,sum;
	int mx_st,mx_se,mx_hi,mx_num;
	int lzy_st,lzy_hi,lzy_se,lzy_he;
	/*
	mx_st 区间最大，mx_se 区间严格次大，mx_hi 区间历史最大，mx_sum 区间最大出现次数
	lzy_st 最大值加减标记，lzy_hi 历史最大值加减标记
	lzy_se 非最大值加减标记，lzy_he 非历史最大值加减标记
	*/
}tr[N<<2];

这里解释一下区间最大出现次数指的是在一个区间 \([l,r]\) 中有几个数是当前区间的最大值。

接下来我们分模块讲一下各个操作：

建树

其他的部分和正常线段树一样，不过因为叶子节点只有一个值，故严格次大值应该附成极小值。

void build(int u,int l,int r){
	tr[u]={l,r};
	if(l==r){
		tr[u].sum=tr[u].mx_st=tr[u].mx_hi=a[l];
		tr[u].mx_num=1;
		tr[u].mx_se=-inf;
		return;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}

上传

我们需要更新的是区间和，最大值，严格次大值，历史最大值，最大值出现次数。

这里说一下不太好弄的严格次大值：显然如果两个儿子的最大值相同，那么严格次大值就是两边的严格次大值的较大的那个。

否则，我们设儿子 \(a\) 的最大值比儿子 \(b\) 的最大值更大，于是严格次大值就是儿子 \(a\) 的严格次大值和儿子 \(b\) 的最大值的较大值。

其它的更新见代码：

void pushup(int u){
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
	tr[u].mx_st=max(tr[u<<1].mx_st,tr[u<<1|1].mx_st);
	tr[u].mx_hi=max(tr[u<<1].mx_hi,tr[u<<1|1].mx_hi);
	if(tr[u<<1].mx_st==tr[u<<1|1].mx_st){
		tr[u].mx_num=tr[u<<1].mx_num+tr[u<<1|1].mx_num;
		tr[u].mx_se=max(tr[u<<1].mx_se,tr[u<<1|1].mx_se);
	}
	else if(tr[u<<1].mx_st>tr[u<<1|1].mx_st){
		tr[u].mx_num=tr[u<<1].mx_num;
		tr[u].mx_se=max(tr[u<<1].mx_se,tr[u<<1|1].mx_st);
	}
	else{
		tr[u].mx_num=tr[u<<1|1].mx_num;
		tr[u].mx_se=max(tr[u<<1].mx_st,tr[u<<1|1].mx_se);
	}
}

下传

这里拆成了两个部分 \(modify\) 和 \(pushdown\)。

先说一下 \(modify\)：

我们传进去的参数有区间最大值，区间历史最大值，区间非最大值和区间非历史最大值这四个玩意要加上的数，同时要更新一堆东西。

  • \(sum\)：区间最大值的个数乘上最大值加上的数，其他的数乘上非最大值加上的数。

  • \(mxhi\)：首先还没有更新的 \(mxst\) 已经是历史了，所以我们要在原来的历史最大值和 \(mxst\) 加上历史最大值加上的数中取最大值。

  • \(mxst\)：比较显然，直接加上最大值要加的数即可。

  • \(mxse\)：如果这个区间有严格次大值，就加上非最大值加上的数。

  • \(lzyhi\)：这时还没有更新的 \(lzyst\) 也已经成为了历史，所以按照 \(mxhi\) 的方式进行更新就行了。

  • \(lzyst\)：直接加上最大值应该加的数即可。

  • \(lzyhe\)：此时的 \(lzyse\) 也已经成为了历史，所以按照 \(lzyhi\) 的方式进行更新即可。

  • \(lzyse\)：直接加上非最大值应该加上的数即可。

然后放一下代码：

void modify(int u,int val_st,int val_hi,int val_se,int val_he){
	tr[u].sum+=(tr[u].mx_num*val_st+(tr[u].r-tr[u].l+1-tr[u].mx_num)*val_se);
	tr[u].mx_hi=max(tr[u].mx_hi,tr[u].mx_st+val_hi);
	tr[u].mx_st+=val_st;
	if(tr[u].mx_se!=-inf)tr[u].mx_se+=val_se;
	tr[u].lzy_hi=max(tr[u].lzy_hi,tr[u].lzy_st+val_hi);
	tr[u].lzy_st+=val_st;
	tr[u].lzy_he=max(tr[u].lzy_he,tr[u].lzy_se+val_he);
	tr[u].lzy_se+=val_se;
}

好了，然后我们继续说 \(pushdown\)：

首先我们记 \(mx\) 为当前区间的最大值，下面我们进行分情况讨论：

如果一个区间的最大值为 \(mx\)，则我们直接按照把四个懒标记传进 \(modify\) 里即可。

否则，都不是最大值，那么我们把应该传进最大值和历史最大值懒标记的部分传进非最大值和历史非最大值的懒标记即可。

下面放一下代码：

void pushdown(int u){
	int maxx=max(tr[u<<1].mx_st,tr[u<<1|1].mx_st);
	if(tr[u<<1].mx_st==maxx)modify(u<<1,tr[u].lzy_st,tr[u].lzy_hi,tr[u].lzy_se,tr[u].lzy_he);
	else modify(u<<1,tr[u].lzy_se,tr[u].lzy_he,tr[u].lzy_se,tr[u].lzy_he);
	if(tr[u<<1|1].mx_st==maxx)modify(u<<1|1,tr[u].lzy_st,tr[u].lzy_hi,tr[u].lzy_se,tr[u].lzy_he);
	else modify(u<<1|1,tr[u].lzy_se,tr[u].lzy_he,tr[u].lzy_se,tr[u].lzy_he);
	tr[u].lzy_st=tr[u].lzy_hi=tr[u].lzy_se=tr[u].lzy_he=0;
}

区间加

非常好做，按照正常线段树的方式直接在区间被完全包含时进行 \(modify\) 即可，所以直接看一下代码就行了：

void modify_add(int u,int L,int R,int v){
	if(tr[u].l>=L&&tr[u].r<=R){
		modify(u,v,v,v,v);
		return;
	}
	int mid=tr[u].l+tr[u].r>>1;
	pushdown(u);
	if(L<=mid)modify_add(u<<1,L,R,v);
	if(R>mid)modify_add(u<<1|1,L,R,v);
	pushup(u);
}

区间取最小值

最后一个比较恶心的东西，考虑一个事情，当前区间最大值已经不比要修改的值大了直接返回就好，但是这样在修改的值极小的时候复杂度会直接炸掉，所以这时就是我们用上之前维护的严格次大值派上用场的时候了。

我们只需要找到 \(mxst< v < mxse\) 的区间修改区间的最大值和历史最大值即可，并且可以把取最小值的操作改成加法操作，所以直接使用 \(modify\) 改就好了。

然后放一下代码：

void modify_min(int u,int L,int R,int v){
	if(tr[u].mx_st<=v)return;
	if(tr[u].l>=L&&tr[u].r<=R&&tr[u].mx_se<v){
		modify(u,v-tr[u].mx_st,v-tr[u].mx_st,0,0);
		return;
	}
	int mid=tr[u].l+tr[u].r>>1;
	pushdown(u);
	if(L<=mid)modify_min(u<<1,L,R,v);
	if(R>mid)modify_min(u<<1|1,L,R,v);
	pushup(u);
}

一堆查询

没啥好说的，按照正常线段树的查法查就行了，代码见最后的代码里。

代码（合集版）

#include<bits/stdc++.h>
#define int long long
#define N 500005
#define inf 2e18
using namespace std;
int n,m,a[N];
struct node{
	int l,r,sum;
	int mx_st,mx_se,mx_hi,mx_num;
	int lzy_st,lzy_hi,lzy_se,lzy_he;
}tr[N<<2];
void pushup(int u){
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
	tr[u].mx_st=max(tr[u<<1].mx_st,tr[u<<1|1].mx_st);
	tr[u].mx_hi=max(tr[u<<1].mx_hi,tr[u<<1|1].mx_hi);
	if(tr[u<<1].mx_st==tr[u<<1|1].mx_st){
		tr[u].mx_num=tr[u<<1].mx_num+tr[u<<1|1].mx_num;
		tr[u].mx_se=max(tr[u<<1].mx_se,tr[u<<1|1].mx_se);
	}
	else if(tr[u<<1].mx_st>tr[u<<1|1].mx_st){
		tr[u].mx_num=tr[u<<1].mx_num;
		tr[u].mx_se=max(tr[u<<1].mx_se,tr[u<<1|1].mx_st);
	}
	else{
		tr[u].mx_num=tr[u<<1|1].mx_num;
		tr[u].mx_se=max(tr[u<<1].mx_st,tr[u<<1|1].mx_se);
	}
}
void build(int u,int l,int r){
	tr[u]={l,r};
	if(l==r){
		tr[u].sum=tr[u].mx_st=tr[u].mx_hi=a[l];
		tr[u].mx_num=1;
		tr[u].mx_se=-inf;
		return;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}
void modify(int u,int val_st,int val_hi,int val_se,int val_he){
	tr[u].sum+=(tr[u].mx_num*val_st+(tr[u].r-tr[u].l+1-tr[u].mx_num)*val_se);
	tr[u].mx_hi=max(tr[u].mx_hi,tr[u].mx_st+val_hi);
	tr[u].mx_st+=val_st;
	if(tr[u].mx_se!=-inf)tr[u].mx_se+=val_se;
	tr[u].lzy_hi=max(tr[u].lzy_hi,tr[u].lzy_st+val_hi);
	tr[u].lzy_st+=val_st;
	tr[u].lzy_he=max(tr[u].lzy_he,tr[u].lzy_se+val_he);
	tr[u].lzy_se+=val_se;
}
void pushdown(int u){
	int maxx=max(tr[u<<1].mx_st,tr[u<<1|1].mx_st);
	if(tr[u<<1].mx_st==maxx)modify(u<<1,tr[u].lzy_st,tr[u].lzy_hi,tr[u].lzy_se,tr[u].lzy_he);
	else modify(u<<1,tr[u].lzy_se,tr[u].lzy_he,tr[u].lzy_se,tr[u].lzy_he);
	if(tr[u<<1|1].mx_st==maxx)modify(u<<1|1,tr[u].lzy_st,tr[u].lzy_hi,tr[u].lzy_se,tr[u].lzy_he);
	else modify(u<<1|1,tr[u].lzy_se,tr[u].lzy_he,tr[u].lzy_se,tr[u].lzy_he);
	tr[u].lzy_st=tr[u].lzy_hi=tr[u].lzy_se=tr[u].lzy_he=0;
}
void modify_add(int u,int L,int R,int v){
	if(tr[u].l>=L&&tr[u].r<=R){
		modify(u,v,v,v,v);
		return;
	}
	int mid=tr[u].l+tr[u].r>>1;
	pushdown(u);
	if(L<=mid)modify_add(u<<1,L,R,v);
	if(R>mid)modify_add(u<<1|1,L,R,v);
	pushup(u);
}
void modify_min(int u,int L,int R,int v){
	if(tr[u].mx_st<=v)return;
	if(tr[u].l>=L&&tr[u].r<=R&&tr[u].mx_se<v){
		modify(u,v-tr[u].mx_st,v-tr[u].mx_st,0,0);
		return;
	}
	int mid=tr[u].l+tr[u].r>>1;
	pushdown(u);
	if(L<=mid)modify_min(u<<1,L,R,v);
	if(R>mid)modify_min(u<<1|1,L,R,v);
	pushup(u);
}
int qry_sum(int u,int L,int R){
	if(tr[u].l>=L&&tr[u].r<=R){
		return tr[u].sum;
	}
	int mid=tr[u].l+tr[u].r>>1;
	int res=0;
	pushdown(u);
	if(L<=mid)res+=qry_sum(u<<1,L,R);
	if(R>mid)res+=qry_sum(u<<1|1,L,R);
	return res;
}
int qry_max(int u,int L,int R){
	if(tr[u].l>=L&&tr[u].r<=R){
		return tr[u].mx_st;
	}
	int mid=tr[u].l+tr[u].r>>1;
	int res=-inf;
	pushdown(u);
	if(L<=mid)res=max(res,qry_max(u<<1,L,R));
	if(R>mid)res=max(res,qry_max(u<<1|1,L,R));
	return res;
}
int qry_hi(int u,int L,int R){
	if(tr[u].l>=L&&tr[u].r<=R){
		return tr[u].mx_hi;
	}
	int mid=tr[u].l+tr[u].r>>1;
	int res=-inf;
	pushdown(u);
	if(L<=mid)res=max(res,qry_hi(u<<1,L,R));
	if(R>mid)res=max(res,qry_hi(u<<1|1,L,R));
	return res;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(m--){
		int op,l,r,k,v;
		cin>>op;
		if(op==1){
			cin>>l>>r>>k;
			modify_add(1,l,r,k);
		}
		else if(op==2){
			cin>>l>>r>>v;
			modify_min(1,l,r,v);
		}
		else if(op==3){
			cin>>l>>r;
			cout<<qry_sum(1,l,r)<<'\n';
		}
		else if(op==4){
			cin>>l>>r;
			cout<<qry_max(1,l,r)<<'\n';
		}
		else{
			cin>>l>>r;
			cout<<qry_hi(1,l,r)<<'\n';
		}
	}
	return 0;
}

标签：lzy,int,线段,tr,mx,司机,st,最大值
From： https://www.cnblogs.com/zxh923aoao/p/18302375

相关文章

  • 线段树——AcWing 245. 你能回答这些问题吗
    目录线段树定义运用情况注意事项解题思路AcWing245.你能回答这些问题吗题目描述运行代码代码思路改进思路线段树定义线段树是一种用于区间查询和更新问题的数据结构。它通过递归地将一个区间分解为若干子区间，每个节点代表一个子区间的和、最小值、最大值等信息，......
  • 一些可以在线段树上维护的信息和修改
    信息最基础的信息之一：区间和\(sum=l.sum+r.sum\)最基础的信息之一：区间大小\(sz=l.sz+r.sz\)最基础的信息之一：区间最值\(minv=min(l.minv,r.minv)\)普通信息：最值个数if(l.minv<r.minv)minvcnt=l.minvcnt;elseif(r.minv<l.minv)minvcnt=r.minvcnt;......
  • 李超线段树
    李超线段树李超线段树发现要维护的问题十分难做，所以我们要引入李超线段树。我们发现，如果在一个区间内，一条线段的整体在另一条线段上方，那么这条线段一定更优，我们称之为最优线段。但是如果并不是这样，应该如何做呢？这里给出线段为一个区间内的最优线段的条件：线段的定义域覆盖了......
  • 中位数（权值线段树版）
    中位数题目描述给定一个长度为NNN的非负整数序列AAA，对于前奇数......
  • 线段树分治学习笔记
    线段树分治是一种通过线段树维护时间轴，实现一些可撤销的信息维护问题的手段。线段树分治是离线算法。具体地，对于若干个修改与询问，按照时间戳像区间修改一样挂在线段树的节点上，然后遍历整棵线段树，将节点上的操作计入贡献，对于一个时间戳为\(t\)的询问，线段树上区间\([t,t]\)即......
  • CF1864F Exotic Queries （离线+线段树+树状数组）
    CF1864FExoticQueries离线+线段树+树状数组先把权值在\([l,r]\)之内的单独拎出来看性质。可以知道策略一定是元素从小到大消成\(0\)。当消除元素\(x\)时，最好的情况当然是一次全消了，但一般元素\(x\)的位置两两之间会有之前消成的\(0\)，将所有位置分成了\(n\)段，那么消......
  • openlayer, 由一个图标遮盖线段需求引发的思考
    最近碰到这么一个需求：有一些面（Polygon）和线（LineString），需要在面的边线上或者在线上均匀绘制一些矩形图标（在各种分辨率下）。在一个Polygon的边线或者LineString上绘制一个矩形图标时，图标会遮住线，如果图标是部分镂空的，就会看到线从图标中穿过，如何让图标看起来遮住了线呢，自然而然就会......
  • GLFLS课程：线段树进阶
    线段树合并与分裂线段树合并两个权值线段树\(T_1\)和\(T_2\)的合并是一个递归的过程。我们不妨设要合并的子树为\(x\)和\(y\)，其对应区间均为\([l,\r]\)那么分类讨论如下：  \((1)\)首先若\(x=0\)或\(y=0\)，则\(x\)，\(y\)中有空节点，直接返回\(x+y\)即可......
  • 【磁力精选】这10个磁力资源搜索网站，用过的都是老司机！
    随着网络技术的发展，磁力资源搜索网站在人们的日常生活中扮演着越来越重要的角色。一款优秀的磁力搜索网站可以帮助用户快速找到所需资源，提高工作学习效率。在这里，我们将介绍另外10个优秀的BT磁力资源搜索网站，只要善加利用，将会让您的效率提升10倍！1-5：51BT神器网址：51bt.site简......
  • 20240706总结（线段树应用）
    A-PhysicalEducationLessonsCF915EPhysicalEducationLessons题解：没什么好说的，动态开点模板题（好像普通线段树也可以做）B-GCDofanArrayCF1493DGCDofanArray题解：暴力分解质因数，修改的时候也把x分解，对每个质数开一个可重集合（multiset）记录一下每个质数出现的不同位......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99