首页 > 其他分享 >【数据结构】吉司机线段树

【数据结构】吉司机线段树

时间：2023-05-31 20:55:04浏览次数：44  
标签：int max 线段 pos mid 司机 maxn 数据结构 最大值

【数据结构】吉司机线段树(Segment Tree Beats)

吉司机线段树，是由杭州学军中学的吉如一在2016年国集论文当中提出的，解决了区间最值操作和区间历史最值问题。

题目描述

给出一个长度为 \(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)\)。

算法描述

对于1、3、4操作，是最基本的线段树区间加，区间求和、求max的操作，详见P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)，我们先来解决操作2，我们发现想要动态探测哪些值大于\(v\)，并进行min操作十分艰难，因为每个大于\(v\)的数不一样，所以每个大于\(v\)的数要减去的数就不一样，很难统计。

那就让区间内大于\(v\)的数只有一个好了。

对于一个区间，我们记录一个最大值\(maxn\)，和一个严格次大值\(sec\)（只有一个值时为\(-inf\)），对于区间取\(min\)操作，我们分为以下三种情况讨论：

1.\(k \geq maxn\)，\(k\)在这个区间之内不能更新任何一个值，直接\(return\)

2.\(maxn > k > sec\)，\(k\)只能更新\(maxn\)，让\(sum -= maxn * cnt\)(区间最大值个数)\(,maxn = k\)，因为要下传操作，所以让\(tag2\)(更新\(maxn\)的\(tag\))减去(\(maxn - k\))

3.\(k \leq sec\),分别向\(lc\)和\(rc\)两边递归更新答案。

这样我们就完成了对最小值的更新，同时向两边递归，会不会影响复杂度？事实上这个操作的复杂度仍然是\(O(logn)\)的，证明如下：
（选自吉如一2016国家集训队论文）

image

image

代码：

inline void modify_min(int l,int r,int L,int R,int k,int pos)
{
	if(k >= t[pos].maxn) return;
	if(L <= l && r <= R && k > t[pos].sec)
	{
		t[pos].sum -= 1ll * t[pos].cnt * (t[pos].maxn - k);
		t[pos].tag2 -= t[pos].maxn - k;
		t[pos].maxn = k;
		return;
	}
	pushdown(pos,l,r);
	int mid = (l + r) >> 1;
	if(L <= mid) modify_min(l,mid,L,R,k,pos << 1);
	if(R > mid) modify_min(mid + 1,r,L,R,k,pos << 1 | 1);
	pushup(pos);
}

现在来看操作5，我们发现，因为修改只有加，一个位置的历史最大值，其实是这个位置原来的值（不一定是原始值，可以看作是pushdown之前的值）加上pushdown之前出现过最大的tag，我们发现在上面的\(modify\_min\)操作中最大值会单独改变，所以区间中的最大值与其他数改变的量（也就是tag）是不一样的，所以我们记录\(tag1\),\(tag2\)代表其他数，最大值的改变量，用\(tag3\),\(tag4\)表示\(tag1\),\(tag2\)在pushdown之前的最大值，这样我们在pushdown的时候就有：

\[history\_max_{pos} = max\{history\_max_{pos},max_{pos} + tag4\} \]

每次更新\(k1\)和\(k3\)的时候，都相应的更新\(k2\)和\(k4\)

其实最难的部分在更新标记上，这里我们先讲上传：

和、最大值、历史最大值都可以左右区间直接合并更新，但是对于次大值和最大值个数，我们分类讨论：

1.\(maxn_{lc} == maxn_{rc}\) : 这个时候次大值应当等于两儿子的次大值取\(max\)，而最大值计数等于两边相加。

2.\(maxn_{lc} > maxn_{rc}\) : 次大值等于左边的次大值和右边的最大值取\(max\)，最大值计数等于左边的\(cnt\)

3.\(maxn_{lc} < maxn_{rc}\) : 次大值等于左边的最大值和右边的次大值取\(max\)，最大值计数等于右边的\(cnt\)

这样就完成了上传

inline void pushup(int pos)
{
	t[pos].sum = t[pos << 1].sum + t[pos << 1 | 1].sum;
	t[pos].maxn = max(t[pos << 1].maxn,t[pos << 1 | 1].maxn);
	t[pos].hismax = max(t[pos << 1].hismax,t[pos << 1 | 1].hismax);
	if(t[pos << 1].maxn == t[pos << 1 | 1].maxn) 
		t[pos].sec = max(t[pos << 1].sec,t[pos << 1 | 1].sec),t[pos].cnt = t[pos << 1].cnt + t[pos << 1 | 1].cnt;
	else if(t[pos << 1].maxn > t[pos << 1 | 1].maxn)
		t[pos].sec = max(t[pos << 1].sec,t[pos << 1 | 1].maxn),t[pos].cnt = t[pos << 1].cnt;
	else 
		t[pos].sec = max(t[pos << 1].maxn,t[pos << 1 | 1].sec),t[pos].cnt = t[pos << 1 | 1].cnt;
}

对于下传，我们也需要分类讨论：
如果全局最大值在左边，那么左边的最大值要按照最大值的方式来更新（即将\(tag2\)和\(tag4\)传下去），否则就将左边不管是不是左边的最大值，都用\(tag1\)和\(tag3\)来更新。

如果全局最大值在右边，同理。

注意这两个条件可以同时成立，不要写else

inline void pushdown(int pos,int l,int r)
{
	int mid = (l + r) >> 1;
	int mx = max(t[pos << 1].maxn,t[pos << 1 | 1].maxn);
	if(mx == t[pos << 1].maxn) change(pos << 1,l,mid,t[pos].tag1,t[pos].tag2,t[pos].tag3,t[pos].tag4);
	else change(pos << 1,l,mid,t[pos].tag1,t[pos].tag1,t[pos].tag3,t[pos].tag3);
	if(mx == t[pos << 1 | 1].maxn) change(pos << 1 | 1,mid + 1,r,t[pos].tag1,t[pos].tag2,t[pos].tag3,t[pos].tag4);
	else change(pos << 1 | 1,mid + 1,r,t[pos].tag1,t[pos].tag1,t[pos].tag3,t[pos].tag3);
	t[pos].tag1 = 0;
	t[pos].tag2 = 0;
	t[pos].tag3 = 0;
	t[pos].tag4 = 0;
}
inline void change(int pos,int l,int r,int k1,int k2,int k3,int k4)
{
	t[pos].sum += 1ll * (r - l + 1 - t[pos].cnt) * k1 + 1ll * t[pos].cnt * k2;
	t[pos].hismax = max(t[pos].hismax,t[pos].maxn + k4);
	t[pos].maxn += k2;
	if(t[pos].sec != -inf) t[pos].sec += k1;
	t[pos].tag4 = max(t[pos].tag4,t[pos].tag2 + k4);
	t[pos].tag3 = max(t[pos].tag3,t[pos].tag1 + k3);
	t[pos].tag1 += k1;
	t[pos].tag2 += k2;
}

注意\(sec\)一行，如果这个节点没有次大值（就是整个区间只有一个值），那么就不能更新值为\(-inf\)的次大值。

区间加时注意要更新全部变量：

inline void modify_add(int l,int r,int L,int R,int k,int pos)
{ 
	if(L <= l && r <= R)
	{
		t[pos].sum += 1ll * k * (r - l + 1 - t[pos].cnt) + 1ll * k * t[pos].cnt;
		t[pos].maxn += k;
		t[pos].hismax = max(t[pos].hismax,t[pos].maxn);
		if(t[pos].sec != -inf) t[pos].sec += k;
		t[pos].tag1 += k;t[pos].tag2 += k;
		t[pos].tag3 = max(t[pos].tag3,t[pos].tag1);
		t[pos].tag4 = max(t[pos].tag4,t[pos].tag2); 
		return;
	}
	pushdown(pos,l,r);
	int mid = (l + r) >> 1;
	if(L <= mid) modify_add(l,mid,L,R,k,pos << 1);
	if(R > mid) modify_add(mid + 1,r,L,R,k,pos << 1 | 1);
	pushup(pos);
}

对最大值，和，历史最大值的查询正常查询就好，注意在建树的时候给次大值附上\(-inf\)的初值

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5,inf = 2e9;
struct Node{
	long long sum;
	int maxn,sec,cnt,hismax,tag1,tag2,tag3,tag4;
}t[N * 4];
int n,m;
inline void pushup(int pos)
{
	t[pos].sum = t[pos << 1].sum + t[pos << 1 | 1].sum;
	t[pos].maxn = max(t[pos << 1].maxn,t[pos << 1 | 1].maxn);
	t[pos].hismax = max(t[pos << 1].hismax,t[pos << 1 | 1].hismax);
	if(t[pos << 1].maxn == t[pos << 1 | 1].maxn) 
		t[pos].sec = max(t[pos << 1].sec,t[pos << 1 | 1].sec),t[pos].cnt = t[pos << 1].cnt + t[pos << 1 | 1].cnt;
	else if(t[pos << 1].maxn > t[pos << 1 | 1].maxn)
		t[pos].sec = max(t[pos << 1].sec,t[pos << 1 | 1].maxn),t[pos].cnt = t[pos << 1].cnt;
	else 
		t[pos].sec = max(t[pos << 1].maxn,t[pos << 1 | 1].sec),t[pos].cnt = t[pos << 1 | 1].cnt;
}
inline void change(int pos,int l,int r,int k1,int k2,int k3,int k4)
{
	t[pos].sum += 1ll * (r - l + 1 - t[pos].cnt) * k1 + 1ll * t[pos].cnt * k2;
	t[pos].hismax = max(t[pos].hismax,t[pos].maxn + k4);
	t[pos].maxn += k2;
	if(t[pos].sec != -inf) t[pos].sec += k1;
	t[pos].tag4 = max(t[pos].tag4,t[pos].tag2 + k4);
	t[pos].tag3 = max(t[pos].tag3,t[pos].tag1 + k3);
	t[pos].tag1 += k1;
	t[pos].tag2 += k2;
}
inline void pushdown(int pos,int l,int r)
{
	int mid = (l + r) >> 1;
	int mx = max(t[pos << 1].maxn,t[pos << 1 | 1].maxn);
	if(mx == t[pos << 1].maxn) change(pos << 1,l,mid,t[pos].tag1,t[pos].tag2,t[pos].tag3,t[pos].tag4);
	else change(pos << 1,l,mid,t[pos].tag1,t[pos].tag1,t[pos].tag3,t[pos].tag3);
	if(mx == t[pos << 1 | 1].maxn) change(pos << 1 | 1,mid + 1,r,t[pos].tag1,t[pos].tag2,t[pos].tag3,t[pos].tag4);
	else change(pos << 1 | 1,mid + 1,r,t[pos].tag1,t[pos].tag1,t[pos].tag3,t[pos].tag3);
	t[pos].tag1 = 0;
	t[pos].tag2 = 0;
	t[pos].tag3 = 0;
	t[pos].tag4 = 0;
}
inline void build(int l,int r,int pos)
{
	if(l == r)
	{
		cin>>t[pos].sum;
		t[pos].maxn = t[pos].sum;
		t[pos].hismax = t[pos].maxn;
		t[pos].sec = -inf;
		t[pos].tag1 = t[pos].tag2 = t[pos].tag3 = t[pos].tag4 = 0;
		t[pos].cnt = 1;
		return;
	}
	int mid = (l + r) >> 1;
	build(l,mid,pos << 1);
	build(mid + 1,r,pos << 1 | 1);
	pushup(pos);
}
inline void modify_add(int l,int r,int L,int R,int k,int pos)
{ 
	if(L <= l && r <= R)
	{
		t[pos].sum += 1ll * k * (r - l + 1 - t[pos].cnt) + 1ll * k * t[pos].cnt;
		t[pos].maxn += k;
		t[pos].hismax = max(t[pos].hismax,t[pos].maxn);
		if(t[pos].sec != -inf) t[pos].sec += k;
		t[pos].tag1 += k;t[pos].tag2 += k;
		t[pos].tag3 = max(t[pos].tag3,t[pos].tag1);
		t[pos].tag4 = max(t[pos].tag4,t[pos].tag2); 
		return;
	}
	pushdown(pos,l,r);
	int mid = (l + r) >> 1;
	if(L <= mid) modify_add(l,mid,L,R,k,pos << 1);
	if(R > mid) modify_add(mid + 1,r,L,R,k,pos << 1 | 1);
	pushup(pos);
}
inline void modify_min(int l,int r,int L,int R,int k,int pos)
{
	if(k >= t[pos].maxn) return;
	if(L <= l && r <= R && k > t[pos].sec)
	{
		t[pos].sum -= 1ll * t[pos].cnt * (t[pos].maxn - k);
		t[pos].tag2 -= t[pos].maxn - k;
		t[pos].maxn = k;
		return;
	}
	pushdown(pos,l,r);
	int mid = (l + r) >> 1;
	if(L <= mid) modify_min(l,mid,L,R,k,pos << 1);
	if(R > mid) modify_min(mid + 1,r,L,R,k,pos << 1 | 1);
	pushup(pos);
}
inline long long query_sum(int l,int r,int L,int R,int pos)
{
	if(L <= l && r <= R) return t[pos].sum;
	pushdown(pos,l,r);
	int mid = (l + r) >> 1;
	long long ret = 0;
	if(L <= mid) ret += query_sum(l,mid,L,R,pos << 1);
	if(R > mid) ret += query_sum(mid + 1,r,L,R,pos << 1 | 1);
	pushup(pos);
	return ret;
}
inline int query_max(int l,int r,int L,int R,int pos)
{
	if(L <= l && r <= R) return t[pos].maxn;
	pushdown(pos,l,r);
	int mid = (l + r) >> 1,ret = -inf;
	if(L <= mid) ret = max(ret,query_max(l,mid,L,R,pos << 1));
	if(R > mid) ret = max(ret,query_max(mid + 1,r,L,R,pos << 1 | 1));
	pushup(pos);
	return ret;
}
inline int query_hismax(int l,int r,int L,int R,int pos)
{
	if(L <= l && r <= R) return t[pos].hismax;
	pushdown(pos,l,r);
	int mid = (l + r) >> 1,ret = -inf;
	if(L <= mid) ret = max(ret,query_hismax(l,mid,L,R,pos << 1));
	if(R > mid) ret = max(ret,query_hismax(mid + 1,r,L,R,pos << 1 | 1));
	pushup(pos);
	return ret;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	build(1,n,1);
	int op,l,r,k;
	for(int i = 1;i <= m;i++)
	{
		cin>>op>>l>>r;
		switch(op)
		{
			case 1:
				cin>>k;
				modify_add(1,n,l,r,k,1);
				break;
			case 2:
				cin>>k;
				modify_min(1,n,l,r,k,1);
				break;
			case 3:
				cout<<query_sum(1,n,l,r,1)<<endl;
				break;
			case 4:
				cout<<query_max(1,n,l,r,1)<<endl;
				break;
			case 5:
				cout<<query_hismax(1,n,l,r,1)<<endl;
				break;
		}
	}
	return 0;
}

"所有的真理，都是符合客观事实的，更是顺着逻辑的。"

标签：int,max,线段,pos,mid,司机,maxn,数据结构,最大值
From： https://www.cnblogs.com/fanghaoyu801212/p/17447315.html

相关文章

  • POJ1151(线段树+扫描线求矩形面积并)
    题目：http://poj.org/problem?id=1151 #include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>usingnamespacestd;constintN=10005;structnode{intl,r;intcov;doublelen;};structline{......
  • POJ2886线段树 Joseph游戏(单点更新)
    题目：WhoGetstheMostCandies? 题意：1.n个人进行Joseph游戏，游戏共p轮（p为思路：用相对坐标来处理，例如这一轮出局的是p，下一个要+m，则p出局时p+1就变成了p（因为是相对坐标），则下一个人应该是p+m-1,再注意循环和m的正负的处理，不要忘了取模。2.求解原始序号时维护一棵线段树，类似上一题插队......
  • POJ2528 线段树+离散化+hash(成段更新)
    题目：Mayor'sposters 题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报思路:这题数据范围很大,直接搞超时+超内存,需要离散化:离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012]我们用不到[-∞,999][1001,1989][1991,1999][2001,2011][201......
  • C/C++数据结构课程设计[2023-05-31]
    C/C++数据结构课程设计[2023-05-31]数据结构课程设计实验（训）指导书所在学院：计算机科学与工程学院编写说明一．实验总体目标《数据结构》是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本实验的目标是，学生能正确理解和熟练掌握常用数据结构和算......
  • 算法与数据结构高手养成-求职提升特训
    算法与数据结构高手养成-求职提升特训download：3w51xuebccom算法和数据结构是计算机科学中非常重要的概念。它们不仅在编程中扮演了关键角色，而且在其他领域如人工智能、机器学习和物联网等也具有广泛的应用。本文将介绍算法和数据结构的定义和重要性。算法的定义算法是指一组用于......
  • poj 2985(并查集+线段树求K大数)
    解题思路：这道题并查集很容易，合并时找到父节点就直接加上去就ok了。关键是如何求K大数，我一直在想用线段树怎么写，一开始想如果直接记录数的大小那肯定是没戏了，借鉴了一下别人的思路：区间[a,b]记录的是所有的数里面，等于a，a+1，a+2，......，b-1，b的个数。看到这里就应该明白了，这里线段树的用法......
  • hdu 4027（线段树）
    题意：给定100000个数，两种操作，0ij表示将ij这段的数字都开根号（向下取整），1ij表示查询ij之间的所有值的和。。。（所有的和都不超过64位）解题思路：这题要做区间的开平方操作，2^64最多可以做8次开平方操作，所以对于每个节点最多只有8次操作，这道题如果lazy思想的话就要保存每个区间被开平方......
  • hdu 3564(线段树+LIS)
    题意：给出1~n的插入顺序，要求每次插入之后的LIS解题思路：这道题确实挺难想的，我最开始想用树状数组每插入一个数就更新一次，如果这么想，那么你就输了。它这里的想法是先将1-n的最终位置都保存起来，然后再一个个去找LIS。这里有点离线算法的意思，至少了解到更新时可以先别急着处理。还有这里......
  • 初级数据结构--插入删除查找表
    插入：头部插入、尾部插入、任意位置插入删除：定位删除查找：值查找、定位查找//定义表typedefstruct{ intdata[MAXSIZE]; intlength;}SqList;//初始化表voidInitSqList(SqList*pl){ inti=0; for(i=0;i<MAXSIZE;i++) pl->data[i]=0; pl->length=0;}//......
  • 【数据结构】图
    图的定义和基本术语边或弧可以关联相应的值，这些值称作边或弧的权，带权图通常称作网。对于无向图G＝(V,{E})，如果边(v,v’)∈E，则称v和v’互为邻接点，或称v和v’相邻接。此时称边(v,v’)依附于顶点v和v’，或边(v,v’)和顶点v和v’相关联。和顶点v相关联的边的数目称为顶点v的度，......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99