（待填坑）【数据结构】笛卡尔树

知识点

一 . 笛卡尔树 Cartesian Tree

笛卡尔树中的节点及元素满足以下两个性质：

① 树中的元素满足二叉搜索树性质，要求按照中序遍历得到的序列为原数组序列

② 树中节点满足堆性质，根节点的值要大于其左右子节点的值

二 . 四毛子算法 Method of Four Russians

（待填坑）

---

模板题 

洛谷 P5854 【模板】笛卡尔树

题目描述

给定一个  的排列 p，构建其笛卡尔树。

即构建一棵二叉树，满足：

1. 每个节点的编号满足二叉搜索树的性质。
2. 节点 i 的权值为 ，每个节点的权值满足小根堆的性质。

输入格式

第一行一个整数 n。

第二行一个排列 ​。

输出格式

设  分别表示节点 i 的左右儿子的编号（若不存在则为 0）。

一行两个整数，分别表示  和 。

输入输出样例

输入 #1

5
4 1 3 2 5

输出 #1

19 21

说明/提示

【样例解释】

【数据范围】

对于 30% 的数据，。

对于 60% 的数据，。

对于 80% 的数据，。

对于 90% 的数据，。

对于 100% 的数据，。

 （待填坑）

#include 
#include 
#include 
#include 
#include 
#define ll long long 
#define re register
using namespace std;
int n,top=0,k=0;
ll int L,R;
const int maxn=1e7+5,INF=0x3f3f3f3f;
int a[maxn],left_tree[maxn],right_tree[maxn],s[maxn];
 
inline 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^48);
		c=getchar();
	}
	return x*f;
}
 
inline void make_tree(int l,int r) //使用单调栈维护建树
{
	for(re int i=l;i<=r;++i)
	{
		k=top;
		while(k&&a[s[k]]>a[i]) k--;
		if(k) right_tree[s[k]] =i;
		if(k1];
		s[++k]=i;
		top=k;
	}
}
 
int main()
{
	n=read();
	for(re int i=1;i<=n;++i)
	{
		a[i]=read();
	}
	make_tree(1,n);
	for(re int i=1;i<=n;++i)
	{
		L^=1ll*i*(left_tree[i]+1); //要转换成long long形式
		R^=1ll*i*(right_tree[i]+1);
	}
	printf("%lld %lld",L,R);
	return 0;
}

 相关练习

1 . 洛谷 P3793 由乃救爷爷

思路：题目很长，但有用的信息缩减得：有个数，个询问，每次询问问区间[l,r]中的最大值。可以用笛卡尔树求RMQ最值。

#include 
#include 
#include 
#include 
using namespace std;
/****随机数生成器，题目已给出****/
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 n,m,s;
const int maxn=20000005;
int a[maxn],ltree[maxn],rtree[maxn],st[105];
 
int query(int l,int r) //找到当前区间的最大值
{
	int rt=st[1];
	for(;;)
	{
		if(l<=rt && rt<=r) return a[rt];
		if(rt
		else rt=ltree[rt];
	}
}
 
void make_tree() //笛卡尔树有两种写法
{
	int top=0;
	for(int i=1;i<=n;++i)
	{
		int k=0;
		while(top&&a[st[top]]<=a[i]) k=st[top--];
		ltree[i]=k;
		if(top) rtree[st[top]]=i;
		st[++top]=i;
	}
	
}
 
int main()
{
	cin>>n>>m>>s;
	srand(s);
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
	}	
	make_tree();
	unsigned long long ans=0;
	int l,r;
	for(int i=1;i<=m;++i)
	{
		l=read()%n+1; r=read()%n+1;
		if(l>r) swap(l,r);
		ans+=query(l,r);
	}
	cout<
	return 0;
}

2 .  洛谷 P1377 [TJOI2011] 树的序

思路：由题得：给一个生成序列，建出一棵笛卡尔树，求字典序最小的可以得到相同笛卡尔树的生成序列，最后进行笛卡尔树的先序遍历。

进行先序遍历的原因：根据二叉搜索树的性质，其先序的字典序最小，先要确认根节点的位置，再确认左子树，最后确认右子树

#include 
#include 
#include 
#include 
using namespace std;
int n,k=0,top=0;
const int maxn=1e7+5;
int a[maxn],st[maxn],ltree[maxn],rtree[maxn];
inline 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^48);
		c=getchar();
	}
	return x*f;
}
 
inline void dfs(int x)
{
	if(x!=0) 
	{
	printf("%d ",x); //输出根节点后进行左右子树的查找
	dfs(ltree[x]);
	dfs(rtree[x]);
	}
}
 
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		int x=read();
		a[x]=i; //转换成输入的值的序号进行建树
	}
	
	for(int i=1;i<=n;++i)
	{
		k=top;
		while(k && a[st[k]]>a[i]) k--;
		if(k) rtree[st[k]]=i;
		if(k1];
		st[++k]=i;
		top=k;
	}
	dfs(st[1]); //从根开始搜索
	return 0;
}