笛卡尔树

Cartesian tree(笛卡尔树)

1.概念

比如拿最小的当根建树，中序遍历是原数组


笛卡尔树是形如上图的一棵树，满足：

①：堆的性质，以上图为例(小根堆),两个儿子的值大于等于他们的父亲

②：二叉搜索树性质：左边子树的下标比根小，右边子树的下标比根大。显然中序遍历可得原数组

③：询问下标为到下标为之间的最小值，就是找的LCA

2.性质

1. 区间最小值(RMQ),是LCA的值，比如上图4和6的LCA是2,表示我们4,6,2这个区间里面的最小值是2
2. 找y左边第一个<=y的数就是y往上看第一个向左拐的数


3.构造(增量法)

对每个前缀考虑


我们发现只有右链是会变的，一旦走到左边，那就不会变了


比如举个例子：该链插入4


就会变成：


因此我们考虑用一个单调栈维护右链：

具体过程就是：

我们倒着for，如果这个数比我们新插入的数大的话，我们就pop，否则就把新加入的数插入变成右儿子（保证右链的单调性），原来pop掉的变为左儿子。

每个元素至多进栈一次，出栈一次，O(n)完成构造

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;

int n,a[N],l[N],r[N];
void build()
{
	stack<int>st;
	int root = 0;
	for(int i = 1;i<=n;i++)
	{
		int last = 0;//在栈里面最后一个被弹出的节点
		while(!st.empty()&&a[st.top()]>a[i])
		{
			last = st.top();
			st.pop();
		}
		if(!st.empty())r[st.top()] = i;//新加入的元素设为栈顶元素的右儿子
		else root = i;
		l[i] = last;
		st.push(i);
	}
	// for(int i = 1;i<=n;i++)
	// 	cout<<"i = "<<i<<" a[i] = "<<a[i]<<" l[i] = "<<l[i]<<" r[i] = "<<r[i]<<endl;
}

int main()
{
	cin>>n;
	for(int i = 1;i<=n;i++)
		cin>>a[i];
	build();

}

/*
7
3 5 1 7 4 6 2
*/

4.用处

能用一个树形的结构去揭示一个序列区间最小值问题，实现把序列问题转化为树上问题

比如：求所有区间的最小值之和

做法一：找到左边第一个小于它的元素，右边第一个小于它的元素,那么它的贡献区间是,那么贡献值就是

做法二：从笛卡尔树的角度看，还是考虑每个数的贡献，即这个数在多少个区间里是最小值，实际上就是看看它的左儿子有多大它的右儿子有多大。相当于多少对点LCA等于这个点本身，也就是左端点选择左子树的点或者这个点本身，右端点选择右子树或者这个点本身。即：

实现了把序列问题转化为树上问题。

eg1笛卡尔树

给你一个的排列。

让你找到一个的排列，满足对于任意区间$l,rp_l,p_{l+1},…,p_rq_l,q_{l+1},…,q_r$的最小值的位置相同。

输出满足条件的字典序最小的。

思路：从笛卡尔树的角度来看，两个序列的最小值位置相同，说明两个序列的笛卡尔树一样。因为要求字典序最小的，我们按照先序遍历把数字填上去。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2010000;

int n,a[N],l[N],r[N],ans[N],cnt;

void dfs(int x)
{
	ans[x] = ++cnt;
	if(l[x])dfs(l[x]);
	if(r[x])dfs(r[x]);
}

void build()
{
	stack<int>st;
	int root = 0;
	for(int i = 1;i<=n;i++)
	{
		int last = 0;//在栈里面最后一个被弹出的节点
		while(!st.empty()&&a[st.top()]>a[i])
		{
			last = st.top();
			st.pop();
		}
		if(!st.empty())r[st.top()] = i;//新加入的元素设为栈顶元素的右儿子
		else root = i;
		l[i] = last;
		st.push(i);
	}
	// for(int i = 1;i<=n;i++)
	// 	cout<<"i = "<<i<<" a[i] = "<<a[i]<<" l[i] = "<<l[i]<<" r[i] = "<<r[i]<<endl;
	dfs(root);
}

int main()
{
	cin>>n;
	for(int i = 1;i<=n;i++)
		cin>>a[i];
	build();
	for(int i = 1;i<=n;i++)
		cout<<ans[i]<<" ";
	cout<<endl;
}

/*
7
3 5 1 7 4 6 2
*/