首页 > 其他分享 >浅谈笛卡尔树

浅谈笛卡尔树

时间:2024-09-30 08:49:59浏览次数:8  
标签:ch sta val 笛卡尔 int dep 浅谈

[介绍(百度百科)](笛卡尔树_百度百科 (baidu.com))

笛卡尔树是一种特定的二叉树数据结构,可由数列构造,在范围最值查询、范围\(top_k\)查询(range top k queries)等问题上有广泛应用。它具有堆的有序性,中序遍历可以输出原数列。笛卡尔树结构由Vuillmin(1980)在解决范围搜索的几何数据结构问题时提出。从数列中构造一棵笛卡尔树可以线性时间完成,需要采用基于的算法来找到在该数列中的所有最近小数。


特殊的\(treap\)

性质

先说性质感觉会更好理解一些

虽然是"树",但是笛卡尔树其实就是对序列的一个转化

对于树上的任意一点x,左右儿子left,right,以及在原序列上的\(pos\)值,有:

  • 树中的元素满足二叉搜索树的性质,要求按照中序遍历得到的序列为原数组序列,各节点的\(pos\)是连续的,\(pos[left]<pos[x]<pos[right]\),(维持原序列的顺序)
  • 树中节点满足堆性质,节点的\(val\)值要大于其左右子节点的\(val\)值,\(val[x]<val[left],val[right]\),(大根此时则恰恰相反

对于笛卡尔树中每个节点都有两个权值\((val,key)\)

建树

原图出处

可以使用线段树,st表这些数据结构维护区间最大值/最小值,但是没有必要,大多数笛卡尔树的题目都可以通过维护一个单调栈来实现\(O(n)\)的建树

  • 使用单调栈维护最右链
  • 每次插入当前的\(i\),在单调栈中不停弹出栈顶,直至栈顶\(fa\)满足\(val_{fa} < val_i\),则最后一次弹出的就是\(j\)
  • 将\(i\)作为\(fa\)的右儿子,\(j\)作为\(i\)的左儿子

模拟一下就是:

对于序列\(a=\{9,3,7,1,8,12,10,20,15,18,5\}\)

  • 添加点\(1\),\(val_1=9\)加入栈
  • 添加点\(2\),弹出点\(1\),点\(1\)就是\(fa\)的左儿子,将\(val_2=3\)加入栈,成为栈顶
  • 添加点\(3\),\(val_3<val_2\),故成为点\(1\)的右儿子
  • .................(见图)

[P5854 【模板】笛卡尔树](P5854 【模板】笛卡尔树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

模板题,求建出树后就可以得到\(ans\)

#include"bits/stdc++.h"

using namespace std;
const int N=1e7+15;
#define inl inline
#define regi register
#define PII pair<int,int>
//#define ll long long
inl int read(void)
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while(isdigit(ch))  x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*f;
}
int rt;int ls[N],rs[N],fa[N],n;

void build(int* a)
{
	stack<int> sta;stack<int>().swap(sta);
	for(int i=1;i<=n;i++)
	{
		int j=0;
		while(!sta.empty()&&a[sta.top()]>a[i])	j=sta.top(),sta.pop();
		if(sta.empty())	rt=i;
		else	rs[sta.top()]=i;
		ls[i]=j;
		sta.push(i);
	}
}
int p[N],tot=0;
stack<int> sta;
void insert(int val)
{
	p[++tot]=val;
	int i=tot;
	while(!sta.empty()&&p[sta.top()]>p[i])	sta.pop();
	if(!sta.empty())
		fa[i]=sta.top(),rs[sta.top()]=i,ls[i]=i-1;
	else	ls[i]=rt,rt=i;
	sta.push(i);
}
struct RMQ
{
	
	int L,R,dep[10015],sz[10015],ans;
	int dfs1(int u)
	{
		dep[u]=dep[fa[u]]+1;
		if(ls[u])	dfs1(ls[u]);
		if(rs[u])	dfs1(rs[u]);
		sz[u]+=sz[ls[u]],sz[u]+=sz[rs[u]];
	}//lca(l,r)=min(val_l,val_r),dfs1->get_dep
	RMQ(int l,int r):L(l),R(r){memset(dep,0,sizeof dep),memset(sz,0,sizeof sz);};
	int get_RMQ(void)
	{	
		int l=L,r=R;dfs1(1);
		int u=l,v=r;
		while(dep[u]!=dep[v])
		{
			if(dep[u]<dep[v])	swap(u,v);
			u=fa[u];
		}
		ans=u;
	}//log_2 n
};
int a[N];
int main(void)
{
	n=read();
	for(int i=1;i<=n;i++)	a[i]=read();
	build(a);
	long long ans1=0,ans2=0;
	for(int i=1;i<=n;i++)	ans1^=1ll*i*(ls[i]+1),ans2^=1ll*i*(rs[i]+1);
	printf("%lld %lld",ans1,ans2);
	return 0;
}

[P4755 Beautiful Pair](P4755 Beautiful Pair - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

有一个数列\({a}\),需要求出有多少数对\((i,j)\)满足\(a_i \times a_j \le \max_{l=i}^j{a_l}\)的数量

有很多人使用的都是线段树分治,但是提到笛卡尔树了,就写一下笛卡尔树分治

笛卡尔树在这些区间最值的地方有着非常不错的性质,考虑分治,区间为\([l,r]\),\(mid=(l+r)/2\),先转化一下式子为\(a_i\le \lfloor \frac{a_{mid}}{a_j} \rfloor\),笛卡尔树满足堆的性质,也满足搜索树的性质,套个\(cdq\)分治

建出笛卡尔树,可以很容易发现,贡献都是\(max\)两边提供的,考虑两边对答案的影响:

1.max的左子树的贡献
2.max的右子树的贡献
3.右边对左边的贡献

再维护一个树状数组

时间复杂度为\(O(n log^2 n)\)

#include"bits/stdc++.h"

using namespace std;
const int N=1e5+15,M=1e9+15;
#define inl inline
#define regi register
#define PII pair<int,int>
#define int long long

inl int read(void)
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while(isdigit(ch))  x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*f;
}
int rt;
struct node
{
	int ls,rs;
}tr[N];
int n;
void build(int* a)
{
	stack<int> sta;stack<int>().swap(sta);
	for(int i=1;i<=n;i++)
	{
		int j=0;
		
		while(!sta.empty()&&a[sta.top()]<a[i])	j=sta.top(),sta.pop();
		if(sta.empty())	rt=i;
		else	tr[sta.top()].rs=i;
		tr[i].ls=j;
		sta.push(i);
	}
}
int ans;
int siz,a[N],b[N];
long long c[N];
#define lowbit(x) x&(-x)
void add(int x,int k){for(;x<=n;x+=lowbit(x))c[x]+=k;}
int query(int x){long long res=0;for(;x;x-=lowbit(x))res+=c[x];return res;}
void solve(int u,int l,int r)
{
	if(u==0)	return ;
	int ls=tr[u].ls,rs=tr[u].rs;
	int mid=u;
	if(mid-l>r-mid)
	{
		for(int i=mid;i<=r;i++)
		{
			int x=upper_bound(b,b+siz+1,b[a[mid]]/b[a[i]])-b;
			if(x)	ans-=query(x-1);
		}
		solve(ls,l,mid-1),add(a[mid],1);
		for(int i=mid;i<=r;i++)
		{
			int x=upper_bound(b,b+siz+1,b[a[mid]]/b[a[i]])-b;
			if(x)	ans+=query(x-1);
		}
		solve(rs,mid+1,r);
	}
	else
	{
		for(int i=l;i<=mid;i++)
		{
			int x=upper_bound(b,b+siz+1,b[a[mid]]/b[a[i]])-b;
			if(x)	ans-=query(x-1);
		}
		solve(rs,mid+1,r),add(a[mid],1);
		for(int i=l;i<=mid;i++)
		{
			int x=upper_bound(b,b+siz+1,b[a[mid]]/b[a[i]])-b;
			if(x)	ans+=query(x-1);
		}
		solve(ls,l,mid-1);
	}
}

signed main(void)
{
	n=read();
	for(int i=1;i<=n;i++)	b[i]=a[i]=read();
	sort(b+1,b+1+n);
	siz=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)	a[i]=lower_bound(b+1,b+1+siz,a[i])-b;
	build(a);
	solve(rt,1,n);
	printf("%lld",ans);
	return 0;
}

标签:ch,sta,val,笛卡尔,int,dep,浅谈
From: https://www.cnblogs.com/empty-space/p/18441111

相关文章

  • 浅谈数据代理
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>Document</title><......
  • Manacher 算法浅谈
    \(Zero.\)\(~~\)前言杂谈认识我的人都喜欢叫我马拉车,如今,马拉车来浅谈Manacher了(不就是某天打板子的时候打错了吗,不就是啪啪打脸了吗)。首先大家需要知道,Manacher不是很常考,但是也是一项必备的算法。当遇到回文串之类的问题时,别人辛辛苦苦打一堆哈希,你用Manacher算法两个并......
  • 轻松编排工作流,浅谈DolphinScheduler如何使用Python调用API接口?
    最近,在做某大型零售企业项目时,有客户用到DolphinScheduler,并咨询是否可以用Python脚本编排工作流?该如何实现?相信有很多人会有这样的疑问,那么,本文将为我们简单分享DolphinScheduler的优势和实际使用。为什么企业数据开发要使用海豚调度?当企业在做数据开发时,任务调度平台会扮演自......
  • 轻松编排工作流,浅谈DolphinScheduler如何使用Python调用API接口?
    最近,在做某大型零售企业项目时,有客户用到DolphinScheduler,并咨询是否可以用Python脚本编排工作流?该如何实现?相信有很多人会有这样的疑问,那么,本文将为我们简单分享DolphinScheduler的优势和实际使用。为什么企业数据开发要使用海豚调度?当企业在做数据开发时,任务调度平台会扮演自动......
  • 浅谈分时电价下含电动汽车的微电网群双层多目标优化调度
    摘要:为解决大规模电动汽车无序充电导致电网出现“峰上加峰”现象,依据电动汽车充电地点的不同将配电网划分为居民区、办公区、商业区微电网,提出基于峰谷差、分时电价、用户充电满意度多目标下的电动汽车充电模式,建立了微电网内运营商峰谷差—用户充电费用少和充电满意度的双盈多目标......
  • 浅谈医院配电系统谐波分析与治理技术方案
    摘要:文章从谐波治理的危害、治理意义、谐波源组成、谐波治理等方面进行了论述。目的在于通过综合整治电网的谐波,有效地改善医院配电系统的安全、可靠、节能。关键词:医院;配电系统;谐波治理0引言配电系统中存在的谐波成分,会导致电力系统的电能品质下降,从而导致电力供应的可靠性下降。......
  • 浅谈如何处理大语言模型训练数据之三开源数据集介绍
    随着最近这些年来基于统计机器学习的自然语言处理的算法的发展,以及信息检索研究的需求,特别是近年来深度学习和预训练语言模型的研究以及国内国外许多大模型的开源,研究人员们构建了多种大规模开源数据集,涵盖了网页、图片、论文、百科等多个领域。在构建大语言模型时,数据的质量和多......
  • 浅谈软件工程
    基本概念软件工程是指导计算机软件开发和维护的一门工程学科,将合理的管理技术和前沿的技术方法结合起来,经济地开发出高质量的软件并有效地维护。软件工程是:①把系统的、规范的、可度量的途径应用于软件开发、运行和维护过程,也就是把工程应用于软件;②研究①中提到的途径。——1......
  • 笛卡尔树
    思路如果说给你一个数组,有\(q\)组询问,询问一个区间的区间和,那么有最原始的做法。维护一个左端点和一个右端点,每次一位一位移动断点,那么时间复杂度是\(n\timesq\),那么如果我们将查询存起来,按一种我们想要的顺序去做呢?我们就可以排序,排序规则就是:B=sqrt(n);boolcmp(node......
  • 浅谈人工智能技术,对社会经济变革的思考
    原创 冰锋血骨 芯原创 2024年09月23日15:44 北京英国DeepMind公司研发的AlphaGo在2016年3月第一次战胜了围棋世界冠军韩国棋手李世石,人工智能(AI,ArtificialIntelligence)第一次映入公众的视野。人工智能是什么?人工智能会想人一样思考吗?人工智能可以应用在哪些领域?人工智......