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

笛卡尔树

时间：2023-08-07 20:14:52浏览次数：35  
标签：ch sta 笛卡尔 int times 节点

Part 1：知识点

笛卡尔树是一种二叉树，每个节点有两个两个值 \((k,w)\)

其中 \(k\) 满足二叉搜索树的性质，\(w\) 满足二叉堆的性质

一些性质

  • 任何子节点的 \(w\) 小于（或大于）父节点的 \(w\)

  • 对于任何父节点，左节点的 \(k\) 小于父节点的 \(k\)，右节点的 \(k\) 大于父节点的 \(k\)

  • 若 \(k\) 值为数组下标，那么任意两个节点 \(u,v\) 的最近公共祖先就是区间 \([u,v]\) 的极值

笛卡尔树的构建

我们以 \(k\) 作为元素下标，\(w\) 作为元素权值，构建一个小根堆

每次插入一个节点 \(x\) 时，我们都只在右链插入。我们从根节点开始往下跳，找到第一个满足 \(w_y>w_x\) 的 \(y\)，然后把 \(x\) 接在 \(fa[y]\) 的右边，把 \(y\) 接在 \(x\) 的左边

可以证明，这样插入是满足笛卡尔树的性质的

由于每个节点只会进出右链一次，所以时间复杂度 \(O(n)\)

Part 2：习题

P5854 【模板】笛卡尔树

建立一个单调栈去维护右链，这个栈单调递增

插入一个节点 \(x\) 时，若栈顶权值大于 \(w_x\) 就弹出

最后将 \(x\) 接在栈顶的右边，将最后一个出栈的元素接在 \(x\) 的左边，并将 \(x\) 入栈

不断重复即可，最后以 sta[1] 作为根节点

#include<bits/stdc++.h>
using namespace std;

const int N=10000010;

int n,a[N];
int sta[N],t,ch[N][2];
long long L,R;

int read() 
{
	int x=0,f=1; 
	char c=getchar();
	while(c<'0' || c>'9') 
	{
		if(c=='-') 
			f=-1; 
		c=getchar();
	}
	while(c>='0' && c<='9') 
	{
		x=(x<<1)+(x<<3)+(c^'0'); 
		c=getchar();
	}
	return x*f;
}

int main()
{
	n=read();
	for(int i=1; i<=n; i++)
		a[i]=read();
	
	sta[++t]=0;
	for(int i=1; i<=n; i++)
	{
		while(t && a[sta[t]]>a[i])
			ch[i][0]=sta[t--];
		ch[sta[t]][1]=i;
		sta[++t]=i;
	}
	
	for(int i=1; i<=n; i++)
	{
		L^=1LL*i*(ch[i][0]+1);
		R^=1LL*i*(ch[i][1]+1);
	}
	
	printf("%lld %lld",L,R);
	
	return 0;
 }

P1377 [TJOI2011] 树的序
满足二叉搜索树性质的是键值 \(k\)，满足堆性质的是插入的顺序

以此构建一棵笛卡尔树后输出中序遍历即可

#include<bits/stdc++.h>
using namespace std;

const int N=100010;

int n,a[N];
int sta[N],t,ch[N][2];

void dfs(int x)
{
	if(x)
		printf("%d ",x);
	if(ch[x][0])
		dfs(ch[x][0]);
	if(ch[x][1])
		dfs(ch[x][1]);
}

int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		int x=0;
		scanf("%d",&x);
		a[x]=i;
	}
	
	sta[++t]=0;
	for(int i=1; i<=n; i++)
	{
		while(t && a[sta[t]]>a[i])
			ch[i][0]=sta[t--];
		ch[sta[t]][1]=i;
		sta[++t]=i;
	}
		
	dfs(sta[1]);
	
	return 0;
 }

P3793 由乃救爷爷

\(n\) 个数，\(m\) 个询问区间最大值，询问随机，\(n,m\leq 2\times 10^7\)

不带修的 \(\rm RMQ\)，显然 \(\rm ST\) 表不可以

利用笛卡尔树的性质三，我们可以将问题转化成求 \(m\) 次 \(\rm LCA\)，可以使用 \(\rm Tarjan\)

但由于这题数据随机，所以我们直接从根节点暴力向下跳即可

#include<bits/stdc++.h>
using namespace std;

const int N=20000010;

int n,m,s,a[N];
int sta[N],t,ch[N][2];
unsigned long long ans;

namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
	    b=((z1<<6)^z1)>>13;
	    z1=((z1&4294967294U)<<18)^b;
	    b=((z2<<2)^z2)>>27;
	    z2=((z2&4294967288U)<<2)^b;
	    b=((z3<<13)^z3)>>21;
	    z3=((z3&4294967280U)<<7)^b;
	    b=((z4<<3)^z4)>>12;
	    z4=((z4&4294967168U)<<13)^b;
	    return (z1^z2^z3^z4);
    }
}

void srand(unsigned x)
{
	using namespace GenHelper;
	z1=x; 
	z2=(~x)^0x233333333U; 
	z3=x^0x1234598766U; 
	z4=(~x)+51;
}

int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

int query(int l,int r)
{
	int cur=sta[1];
	while(1)
	{
		if(l<=cur && cur<=r)
			return a[cur];
		if(cur<l)
			cur=ch[cur][1];
		else
			cur=ch[cur][0];
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&s);
	srand(s);
	
	for(int i=1; i<=n; i++)
		a[i]=read();
	
	sta[++t]=0;
	for(int i=1; i<=n; i++)
	{
		while(t && a[sta[t]]<a[i])
			ch[i][0]=sta[t--];
		ch[sta[t]][1]=i;
		sta[++t]=i;
	}
	
	for(int i=1; i<=m; i++)
	{
		int l=read()%n+1;
		int r=read()%n+1;
		if(l>r)
			swap(l,r);
		ans+=(unsigned long long)query(l,r);
	}
	
	printf("%llu",ans);
	
	return 0;
 }

P6453 [COCI2008-2009#4] PERIODNI

（双倍经验）

一道笛卡尔树的经典题目

以 \(h_i\) 为权值建立一颗小根线段树

这样做之后可以将原表格横向切割分成若干个矩形，当前矩形的长为 \(size[x]\)，高为 \(h[x]-h[fa]\)。接下来我们就可以在笛卡尔树上进行树形 \(\rm dp\)

设 \(f[x][i]\) 表示在以 \(x\) 为根的子树内放 \(i\) 个数的方案数，则枚举左右子树（用 \(l,r\) 表示）放数的个数 \(j,t\)，就有方程

\[f[x][i]=\sum_{j+t\leq i}f[l][j]\times f[r][t]\times \binom{size[x]-j-t}{i-j-t}\times\binom{h[x]-h[fa]}{i-j-t}\times (i-j-t)! \]

后面的那坨组合数与阶乘相乘表示在当前节点表示的矩形当中放 \(i-j-t\) 个数的方案数。因为子树中放了 \(j+t\) 所以长度要减它们，阶乘表示选出的行和列的对应方案

注意到后面的式子只和 \(j+t\) 有关，所以将式子变换一下

\[f[x][i]=\sum_{s\leq i}{\binom{size[x]-s}{i-s}\times\binom{h[x]-h[fa]}{i-s}\times(i-s)!\:}\times \sum_{j+k=s}{f[l][j]\times f[r][k]} \]

后面那坨式子可以 \(O(n^2)\) 预处理出来，所以总的时间复杂度 \(O(n^3)\)

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=510,M=1000010;
const LL MOD=1e9+7;

int n,k,a[N],ch[N][2],sta[N],t,size[N];
LL fac[M],inv[M],f[N][N],g[N][N];

LL ksm(int x,int y)
{
	LL res=1;
	while(y)
	{
		if(y&1)
			res=(1LL*res*x)%MOD;
		x=1LL*x*x%MOD;
		y>>=1;
	}
	return res;
}

void prework()
{
	fac[0]=inv[0]=1;
	for(int i=1; i<=M-10; i++)
	{
		fac[i]=(fac[i-1]*i)%MOD;
		inv[i]=ksm(fac[i],MOD-2);
	}
}

LL C(int x,int y)
{
	if(y>x)
		return 0;
	return fac[x]*inv[x-y]%MOD*inv[y]%MOD;	
}

void dfs(int x,int fa)
{
	if(ch[x][0])
		dfs(ch[x][0],x);
	if(ch[x][1])
		dfs(ch[x][1],x);
		
	size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
	int h=a[x]-a[fa];
	LL tmp=0;
	
	for(int i=0; i<=size[ch[x][0]]; i++)
		for(int j=0; j<=size[ch[x][1]]; j++)
			(g[x][i+j]+=f[ch[x][0]][i]*f[ch[x][1]][j]%MOD)%=MOD;
	
	for(int i=0; i<=size[x]; i++)
		for(int j=0; j<=size[x]-1; j++)
			(f[x][i]+=g[x][j]*C(size[x]-j,i-j)%MOD*C(h,i-j)%MOD*fac[i-j]%MOD)%=MOD;
}

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	
	sta[++t]=0;
	for(int i=1; i<=n; i++)
	{
		while(t && a[sta[t]]>a[i])
			ch[i][0]=sta[t--];
		ch[sta[t]][1]=i;
		sta[++t]=i;	
	}	
	
	prework();
	
	f[0][0]=1;
	dfs(sta[0],0);
	
	printf("%lld",f[sta[1]][k]);	
	return 0;
}

标签：ch,sta,笛卡尔,int,times,节点
From： https://www.cnblogs.com/xishanmeigao/p/17612585.html

相关文章

  • 笛卡尔树
    模板boolflag=0;while(h[i]<h[sta[top]]) top--,flag=1;cr[sta[top]]=i;if(flag) cl[i]=sta[top+1];sta[++top]=i;受限制的排列对于一个 111 到 nnn 的排列 p1, p2, ⋯ , pnp_1, p_2, \cdots, p_np1​, p2​, ⋯, pn​ ，我们可以轻松地对于任意......
  • pytest + yaml 框架 -47.parameters参数化支持笛卡尔积
    前言v1.3.8版本对parameters参数化格式重新做了定义，支持笛卡尔积了。当然以前旧版本的格式还是继续兼容。parameters参数化新版本对parameters参数化重新做了定义，简化了步骤，更加清晰简洁.1.只有一个变量需要参数化的情况test_p1.ymlconfig:parameters:x:["a"......
  • [数据结构]笛卡尔树、ST表、带权并查集
    Cartesiantree(笛卡尔树)1.概念比如拿最小的当根建树，中序遍历是原数组2.性质区间最小值(RMQ),LCA的值，比如上图4和6的LCA是2,表示我们4,6,2这个区间里面的最小值是2找y左边第一个<=y的数就是y往上看第一个向左拐的数3.构造(增量法)对每个前缀考虑我们发现只有右链是......
  • 数据库关联查询--笛卡尔积
    概念笛卡尔乘积是指在数学中，两个集合X和Y的笛卡尔积（Cartesianproduct），又称直积，表示为X×Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员.设A和B是两个集合，存在一个集合，他的元素是用A中元素为第一元素，B中元素为第二元素构成的有序二元组。称它为A和B的笛卡......
  • 笛卡尔树
    笛卡尔树下文的资料多摘自OIWiki性质笛卡尔树是一种二叉树，每一个节点都由一个键值二元组\((k,w)\)构成。要求\(k\)满足二叉搜索树的性质，而\(w\)满足堆的性质。如果笛卡尔树的\(k\)，\(w\)键值确定的话，且\(k\)互不相同，\(w\)互不相同，那么这个笛卡尔树的结构是唯一的。......
  • 笛卡尔树Kattis-Scaffolding
    笛卡尔树Kattis-Scaffolding注释已经写在代码里了，注意下建树就行#include<bits/stdc++.h>/*先对题意进行分析，每次带m根柱子，进行x轮，每次往左/右/上搭建，问x的最小值？一开始在想，怎么就会有最小值呢？后来发现题目说不能往下走我们还是把图看成一棵树就是说你可以向两个子节点去走，......
  • 笛卡尔树
    性质其节点具有\(2\)个权值，分别是\((key,val)\)，以\(key\)看，其为一颗二叉搜索树，以\(val\)看，其为一个堆（定义）。二叉搜索树：左子树如果不空，则其权值一定小于根节点；右子树如果不空，则其权值一定大于根节点。堆：完全二叉树，每个节点的值大于等于（或小于等于）其子树中的每个节......
  • @黎耀天 发扬 笛卡尔， @物空必能 发扬 牛顿， 无敌了 。
    @黎耀天发扬笛卡尔， @物空必能发扬牛顿，  @joywee2007 发扬爱因斯坦和老子，  无敌了 。 这篇文章的灵感来自 昨前天 看到 @物空必能在牛顿吧发的 《物质的弹性与屈服强度——力学就应当探究力的问题》    https://tieba.baidu.com/p/83932......
  • C++ 树进阶系列之笛卡尔树的两面性
    1.前言笛卡尔树是一种特殊的二叉树数据结构，融合了二叉堆和二叉搜索树两大特性。笛卡尔树可以把数列(组)对象映射成二叉树，便于使用笛卡尔树结构的逻辑求解数列的区间最值或......
  • 笛卡尔树~cartesian-tree
    笛卡尔树简介笛卡尔树是一种平衡树，它的结构和treap相同，但是由于它能在O(n)时间构造，同时具有一些很有意思的性质。构造笛卡尔树的节点由键值对\((k,w)\)组成。其中键......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99