首页 > 其他分享 >线段树-山海经 题解

线段树-山海经 题解

时间：2024-02-20 17:24:59浏览次数：16  
标签：山海经 rzb 题解 线段 ranzb ans rm lzb id

《最痛苦的一集》

从开始的找维护变量 到依据i比较 依据y比较 最后发现问题出在没初始化(
如果不将答案赋值为极小值 那么它最小值就是0
因此 wa了无数遍

下面是思路

首先 要维护的变量有：
\(区间的左右边界 \,l,\,r\)
\(区间的答案 \,ans\)
\(含左端点最大值\,lans\,和含右端点最大值\,rans\)
\(最大值的左右端点 \,lzb,\,yzb\)
\(左答案右端点\,lanzb\,和右答案左端点\,ranzb\)
\(以及区间总和\,sum\)

其次 是update的内容：

  1. 答案更新
    \(ans\)由它的子节点传导而来的路径有三条：
    1>由左子答案传递
    2>由右子答案传递
    3>由左子的右答案和右子的左答案合并而来
    还有需要注意的是一定要尽量选取较小的i与j值 才能符合题意
    表示出来就是（写复杂了
if(rm[id].ans<=rm[id*2].ans)
{
	if(rm[id].ans==rm[id*2].ans)
	{
		if(rm[id].lzb>rm[id*2].lzb)
		{
			rm[id].lzb=rm[id*2].lzb;
			rm[id].rzb=rm[id*2].rzb;
		}
		else if(rm[id].lzb==rm[id*2].lzb&&rm[id].rzb>rm[id*2].rzb)
		{
			rm[id].lzb=rm[id*2].lzb;
			rm[id].rzb=rm[id*2].rzb;
		}
	}
	else
	{
		rm[id].ans=rm[id*2].ans;
		rm[id].lzb=rm[id*2].lzb,rm[id].rzb=rm[id*2].rzb;
	}
}
if(rm[id].ans<=rm[id*2+1].ans)
{
	if(rm[id].ans==rm[id*2+1].ans)
	{
		if(rm[id].lzb>rm[id*2+1].lzb)
		{
			rm[id].lzb=rm[id*2+1].lzb;
			rm[id].rzb=rm[id*2+1].rzb;
		}
		else if(rm[id].lzb==rm[id*2+1].lzb&&rm[id].rzb>rm[id*2+1].rzb)
		{
			rm[id].lzb=rm[id*2+1].lzb;
			rm[id].rzb=rm[id*2+1].rzb;
		}
	}
	else
	{
		rm[id].ans=rm[id*2+1].ans;
		rm[id].lzb=rm[id*2+1].lzb,rm[id].rzb=rm[id*2+1].rzb;
	}
}
if(rm[id].ans<=rm[id*2].rans+rm[id*2+1].lans)
{
	if(rm[id].ans==rm[id*2].rans+rm[id*2+1].lans)
	{
		if(rm[id].lzb>rm[id*2].ranzb)
		{
			rm[id].ans=rm[id*2].rans+rm[id*2+1].lans;
			rm[id].lzb=rm[id*2].ranzb,rm[id].rzb=rm[id*2+1].lanzb;
		}
		else if(rm[id].lzb==rm[id*2].ranzb&&rm[id].rzb>rm[id*2+1].lanzb)
		{
			rm[id].ans=rm[id*2].rans+rm[id*2+1].lans;
			rm[id].lzb=rm[id*2].ranzb,rm[id].rzb=rm[id*2+1].lanzb;
		}
	}
	else
	{
		rm[id].ans=rm[id*2].rans+rm[id*2+1].lans;
		rm[id].lzb=rm[id*2].ranzb,rm[id].rzb=rm[id*2+1].lanzb;
	}
}
  1. 左右答案更新
    这一步较为简单 只有两种情况
    1>由 左/右 子的 左/右 答案传递
    2>由 左/右 的总和加上 右/左 的 左/右 答案迷迷糊糊
    代码如下 有一个小点需单独注意 就是判断时的取等问题
    在取左答案时 要取尽量小的\(j\) 所以取等时更新
    而在取右答案时 要尽量取小\(i\) 所以取等时不更新
    code：
if(rm[id*2+1].rans>rm[id*2+1].sum+rm[id*2].rans)
{
	rm[id].rans=rm[id*2+1].rans;
	rm[id].ranzb=rm[id*2+1].ranzb;
}
else
{
	rm[id].rans=rm[id*2+1].sum+rm[id*2].rans;
	rm[id].ranzb=rm[id*2].ranzb;
}
if(rm[id*2].lans>=rm[id*2].sum+rm[id*2+1].lans)
{
	rm[id].lans=rm[id*2].lans;
	rm[id].lanzb=rm[id*2].lanzb;
}
else
{
	rm[id].lans=rm[id*2].sum+rm[id*2+1].lans;
	rm[id].lanzb=rm[id*2+1].lanzb;
}

剩下的 便是查询了 由于我一开始将update写错了位置 导致以上内容需要写两遍。。

总之 一道很好的线段树 使我的线段旋转 思路找起来不是很费劲 主要是代码。。

code：

OwO 
#include <bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)++)
#define foo(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
using namespace std;
typedef long long ll;
inline int qr()
{
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return f*x;
}
#define qr qr()
const int Ratio=0;
const int N=200005;
const int maxx=INT_MAX;
int n,m;
int a[N];
struct stre
{
	int l,r,sum;
	int lans=-maxx,rans=-maxx,ans=-maxx;//zuiyou zuo you
	int lzb,rzb;//zuiyouduandian
	int lanzb,ranzb;//
}rm[N<<2];
void update(int id)
{
	rm[id].sum=rm[id*2].sum+rm[id*2+1].sum;
	if(rm[id].ans<=rm[id*2].ans)
	{
		if(rm[id].ans==rm[id*2].ans)
		{
			if(rm[id].lzb>rm[id*2].lzb)
			{
				rm[id].lzb=rm[id*2].lzb;
				rm[id].rzb=rm[id*2].rzb;
			}
			else if(rm[id].lzb==rm[id*2].lzb&&rm[id].rzb>rm[id*2].rzb)
			{
				rm[id].lzb=rm[id*2].lzb;
				rm[id].rzb=rm[id*2].rzb;
			}
		}
		else
		{
			rm[id].ans=rm[id*2].ans;
			rm[id].lzb=rm[id*2].lzb,rm[id].rzb=rm[id*2].rzb;
		}
	}
	if(rm[id].ans<=rm[id*2+1].ans)
	{
		if(rm[id].ans==rm[id*2+1].ans)
		{
			if(rm[id].lzb>rm[id*2+1].lzb)
			{
				rm[id].lzb=rm[id*2+1].lzb;
				rm[id].rzb=rm[id*2+1].rzb;
			}
			else if(rm[id].lzb==rm[id*2+1].lzb&&rm[id].rzb>rm[id*2+1].rzb)
			{
				rm[id].lzb=rm[id*2+1].lzb;
				rm[id].rzb=rm[id*2+1].rzb;
			}
		}
		else
		{
			rm[id].ans=rm[id*2+1].ans;
			rm[id].lzb=rm[id*2+1].lzb,rm[id].rzb=rm[id*2+1].rzb;
		}
	}
	if(rm[id].ans<=rm[id*2].rans+rm[id*2+1].lans)
	{
		if(rm[id].ans==rm[id*2].rans+rm[id*2+1].lans)
		{
			if(rm[id].lzb>rm[id*2].ranzb)
			{
				rm[id].ans=rm[id*2].rans+rm[id*2+1].lans;
				rm[id].lzb=rm[id*2].ranzb,rm[id].rzb=rm[id*2+1].lanzb;
			}
			else if(rm[id].lzb==rm[id*2].ranzb&&rm[id].rzb>rm[id*2+1].lanzb)
			{
				rm[id].ans=rm[id*2].rans+rm[id*2+1].lans;
				rm[id].lzb=rm[id*2].ranzb,rm[id].rzb=rm[id*2+1].lanzb;
			}
		}
		else
		{
			rm[id].ans=rm[id*2].rans+rm[id*2+1].lans;
			rm[id].lzb=rm[id*2].ranzb,rm[id].rzb=rm[id*2+1].lanzb;
		}
	}
	if(rm[id*2+1].rans>rm[id*2+1].sum+rm[id*2].rans)
	{
		rm[id].rans=rm[id*2+1].rans;
		rm[id].ranzb=rm[id*2+1].ranzb;
	}
	else
	{
		rm[id].rans=rm[id*2+1].sum+rm[id*2].rans;
		rm[id].ranzb=rm[id*2].ranzb;
	}
	if(rm[id*2].lans>=rm[id*2].sum+rm[id*2+1].lans)
	{
		rm[id].lans=rm[id*2].lans;
		rm[id].lanzb=rm[id*2].lanzb;
	}
	else
	{
		rm[id].lans=rm[id*2].sum+rm[id*2+1].lans;
		rm[id].lanzb=rm[id*2+1].lanzb;
	}
}
void build(int id,int l,int r)
{
	rm[id].l=l,rm[id].r=r;
	if(l==r)
	{
		rm[id].sum=rm[id].ans=rm[id].lans=rm[id].rans=a[l];
		rm[id].lanzb=rm[id].ranzb=rm[id].lzb=rm[id].rzb=l;
		return;
	}
	int mid=(l+r)>>1;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	update(id);
}
stre que(int id,int l,int r)
{	
	if(rm[id].l>=l&&rm[id].r<=r)
	{
		return rm[id];
	}
	int mid=(rm[id].l+rm[id].r)>>1;
	if(l>mid)
		return que(id*2+1,l,r);
	else if(r<=mid)
		return que(id*2,l,r);
	else
	{
		stre ans,ll,rr;
		ll=que(id*2,l,r);
		rr=que(id*2+1,l,r);
		ans.l=ll.l,ans.r=rr.r;
		ans.sum=ll.sum+rr.sum;
		
		if(ans.ans<=ll.ans)
		{
			if(ans.ans==ll.ans)
			{
				if(ans.lzb>ll.lzb)
				{
					ans.lzb=ll.lzb;
					ans.rzb=ll.rzb;
				}
				else if(ans.lzb==ll.lzb&&ans.rzb>ll.rzb)
				{
					ans.lzb=ll.lzb;
					ans.rzb=ll.rzb;
				}
			}
			else
			{
				ans.ans=ll.ans;
				ans.lzb=ll.lzb,ans.rzb=ll.rzb;
			}
		}
		if(ans.ans<=rr.ans)
		{
			if(ans.ans==rr.ans)
			{
				if(ans.lzb>rr.lzb)
				{
					ans.lzb=rr.lzb;
					ans.rzb=rr.rzb;
				}
				else if(ans.lzb==rr.lzb&&ans.rzb>rr.rzb)
				{
					ans.lzb=rr.lzb;
					ans.rzb=rr.rzb;
				}
			}
			else
			{
				ans.ans=rr.ans;
				ans.lzb=rr.lzb,ans.rzb=rr.rzb;
			}
		}
		if(ans.ans<=ll.rans+rr.lans)
		{
			if(ans.ans==ll.rans+rr.lans)
			{
				if(ans.lzb>ll.ranzb)
				{
					ans.ans=ll.rans+rr.lans;
					ans.lzb=ll.ranzb,ans.rzb=rr.lanzb;
				}
				else if(ans.lzb==ll.ranzb&&ans.rzb>rr.lanzb)
				{
					ans.ans=ll.rans+rr.lans;
					ans.lzb=ll.ranzb,ans.rzb=rr.lanzb;
				}
			}
			else
			{
				ans.ans=ll.rans+rr.lans;
				ans.lzb=ll.ranzb,ans.rzb=rr.lanzb;
			}
		}
		if(rr.rans>rr.sum+ll.rans)
		{
			ans.rans=rr.rans;
			ans.ranzb=rr.ranzb;
		}
		else
		{
			ans.rans=rr.sum+ll.rans;
			ans.ranzb=ll.ranzb;
		}
		if(ll.lans>=ll.sum+rr.lans)
		{
			ans.lans=ll.lans;
			ans.lanzb=ll.lanzb;
		}
		else
		{
			ans.lans=ll.sum+rr.lans;
			ans.lanzb=rr.lanzb;
		}
		return ans;
	}
}
int main()
{
//	freopen("hill2.in","r",stdin);
	n=qr,m=qr;
	fo(i,1,n)
		a[i]=qr;
	build(1,1,n);
	fo(i,1,m)
	{
		int aa=qr,bb=qr;
		stre aaaaa=que(1,aa,bb);
		printf("%d %d %d\n",aaaaa.lzb,aaaaa.rzb,aaaaa.ans);
	}
	return Ratio;
}

标签：山海经,rzb,题解,线段,ranzb,ans,rm,lzb,id
From： https://www.cnblogs.com/DrRatio-DanhengYinyue1007/p/18023591

相关文章

  • 【解题报告】【比赛复现】洛谷入门赛 #17 题解
    洛谷入门赛#17题解今日推歌：《春嵐feat.初音ミク》john感觉这首都快成周榜战神了（Before关于我做入门赛的精神状态：没做T4，因为题面读得我头疼……而且大模拟不想做（虽然也不是多大的模拟展开目录目录洛谷入门赛#17题解BeforeA食堂B数学选择题AfterC风球E式神考核Af......
  • CF1905D Cyclic MEX 题解
    题意：给定一个长度为\(n\)的排列\(a\)，\(a_i\in[0,n-1]\)。你可以将这个排列进行循环移位，最小化\(\sum_{i=1}^{n}\text{mex}_{j=1}^ia_j\)的值。首先我们可以先计算出最初情况下每一个\(i\)位置的\(\text{mex}\)值。这个序列一定是单调非严格递增的。首先有一个比......
  • CF1893B Neutral Tonality 题解
    很巧妙的一道题。为了让\(\text{LIS}\)长度最小，我们肯定先将\(b\)数组降序排序，这样\(b\)自身对\(\text{LIS}\)的贡献最小。考虑是否存在一种插入方式使得最终\(a\)的\(\text{LIS}\)长度和最初\(a\)的\(\text{LIS}\)长度相等。这时我们会发现，如果我们插入\(b\)......
  • 线段树
    线段树算是树状数组的进阶版了，树状数组能做的，线段树也肯定能做，它做不了的，线段树也能做。但确实线段树的代码量也很让人挠头，基本原理不再解释。先看一下基础的模板吧单点修改和区间查询点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=300000;intn......
  • CF638C题解
    我们可以针对一个顶点只能同时修一条边这个条件设计方案。由于每条边都要修一遍，同样某天修理的方案放在哪一天修都无所谓，我们采用贪心的策略，在原有的方案上尽可能多地修边。根据上面的性质，我们只需要将同一顶点的边放在不同的某天修理的方案中，使方案尽可能的少即可。跑一遍dfs......
  • "山海经“ 讲解----线段树
    ”山海经“--线段树讲解1、题面：http://cogs.pro/cogs/problem/problem.php?pid=7752、题目大意及分析：i：大概就是说给了你一段[1,n]的区间，并给了每个区间的权值，下面会有m个问题，每个问题给你一段[1,n]的子区间[i,j]，问你在这段区间上的任意一端子区间和最大是多少，并且要求输出这......
  • Docker 使用遇到的问题解决 更改Tag
    dockertagconsul:1.15.4consul:latestdockerrmiconsul:1.15.4删除制定版本在运行时，有些镜像拉取时报错我这里 时 consu,只能制定版本下载1.15.4Errorresponsefromdaemon:manifestforconsul:latestnotfound:manifestunknown:manifestunknown ......
  • P2171 Hz吐泡泡 题解
    传送门题目背景Hz大大是一种可爱的动物（神）。他很喜欢吐泡泡（更喜欢写作业）。题目描述这天，Hz大大心血来潮，吐了n个不同的泡泡玩（保证没有重复的泡泡）。因为他还要写作业，所以他请你帮他把这些泡泡排序成树（左子树<=根<右子树）。输出它的后序遍历。输入格式共2行。第一行，1个整数n。(1<......
  • 洛谷P10179 题解
    题意简述给定\(n\)个点，要求构造出一棵树，同时有\(m\)个事件，第\(i\)个事件要求\(u_i\)和\(v_i\)用两条树边连接，即当中相隔一个点。若存在构造方案，输出Yes并输出其中一种方案，否则输出No。思维路径首先简化问题，假如我们想让一堆点互相相隔一个点，我们的做法。考虑菊花......
  • 线段树的各种板板~(*^▽^*)
    $\color{purple}{板板}$#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineinf0x3f#defineINF0x3f3f3f3f#definemst(a,b)memset(a,b,sizeof(a))#defineElaina0#definelid(id<<1)#definerid(id<<1|1)//即ridco......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99