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

线段树-山海经 题解

时间:2024-02-20 17:24:59浏览次数:25  
标签:山海经 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......