• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

洛谷 P5854 【模板】笛卡尔树

admin

11月 28, 2021

传送门


前置知识

单调栈

笛卡尔树

定义

每个节点都由一个键值二元组构成(x,y)。
要求构建一棵树,满足:

  1. x上是一个二叉搜索树(左儿子<根<右儿子)
  2. y上是一个小根堆

构建过程

于是我们可以按照x值从小到大将节点加入笛卡尔树中。
新加入的点now一定要放在某个节点的右儿子上(或者根节点)(因为需要满足条件1)
然后我们从根节点一直向右走,遇到的第一个y值大于now的y值的点,就不能往下走了(因为需要满足条件2),这时将这个节点设置成now的左儿子,把now代替掉这个节点的位置,就能满足要求。
这个过程可以维护一个单调递增栈来记录这个从根节点一直往右走的路径。

性质与应用

当节点的x,y都给定且不相同时,笛卡尔树是确定唯一的。
可以用来处理区间RQM,两个节点的LCA即为答案。
还有什么结合+1/-1 RMQ在线解决RQM问题的我根本不会

AC代码

#include<cstdio>
#include<iostream>
#include<stack>
using namespace std;
const int maxn=1e7+5;
int n,a[maxn];
long long l[maxn],r[maxn],ans1,ans2;
stack<int> s;
inline char rc()
{
	static char buf[1000000],*pn=buf,*pe=buf;
	return (pn==pe)&&(pe=(pn=buf)+fread(buf,1,1000000,stdin),pn==pe)?EOF:*pn++;
}
inline int read()
{
	int f=0;
	char cc=rc();
	while(cc<'0'||cc>'9')cc=rc();
	while(cc>='0'&&cc<='9')f=f*10+cc-'0',cc=rc();
	return f;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		a[i]=read();
		while(!s.empty()&&a[s.top()]>a[i]) l[i]=s.top(),s.pop();
		if(!s.empty()) r[s.top()]=i;
		s.push(i);
	}
	for(int i=1;i<=n;i++) ans1=ans1^(i*(l[i]+1)),ans2=ans2^(i*(r[i]+1));
	printf("%lld %lld",ans1,ans2);
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。