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

笛卡尔树

时间:2024-04-25 13:14:19浏览次数:12  
标签:右链 笛卡尔 int 元素 st isdigit

笛卡尔树实际上就是对于多个二元组 \((k_i,w_i)\) 的一棵树,使其所有 \(k\) 值满足二叉搜索树的性质,且所有 \(w\) 值都满足小根堆的性质。

在构建时,对于右链上的元素,自底向上一定是 \(w\) 值由小到大的,且一定 \(k\) 值从小到大。

所以我们按 \(k\) 值从小到大排序,比并按顺序插入右链中。

假设我们轮到第 \(i\) 个元素插入,我们先找到在第一个右链中 \(w\) 值大于 \(w_i\) 的元素下标 \(j\) 。因为这棵树需要满足二叉搜索树的性质,所以我们将 \(j\) 以下的元素接到 \(i\) 的左子树上,并将 \(i\) 接到 \(j\) 的右子树上。

使用栈模拟即可。

代码:

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

const int N=1e7+10;
int n;
int st[N],top;
int p[N],ls[N],rs[N];

inline int read(){
	int x=0;
	char c='&';
	while(!isdigit(c))c=getchar();
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}

signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	n=read();
//	cout<<n<<endl;
	for(int i=1;i<=n;i++)p[i]=read();
	for(int i=1;i<=n;i++){
		int k=top;
		while(k>0&&p[st[k]]>p[i])k--;
		if(k)rs[st[k]]=i;
		if(k<top)ls[i]=st[k+1];
		top=k;
		st[++top]=i;
	}
	int ans1=0,ans2=0;
	for(int i=1;i<=n;i++){
		ans1=ans1^(i*(ls[i]+1));
		ans2=ans2^(i*(rs[i]+1));
	}
	cout<<ans1<<" "<<ans2;
	
	return 0;
} 

标签:右链,笛卡尔,int,元素,st,isdigit
From: https://www.cnblogs.com/little-corn/p/18157428

相关文章

  • vue 商品sku添加,笛卡尔算法,商品添加。动态生成table,table添加值后 再生成的table 不
     <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>快速入门</title><!--引入组件库--><linkrel="stylesheet"href="https://un......
  • vue 商品sku,笛卡尔算法,商品添加。动态生成table,table添加值后 再生成的table 不改变t
     <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>快速入门</title><!--引入组件库--><linkrel="stylesheet"href="https://un......
  • 笛卡尔树
    1定义笛卡尔树是一种二叉树,每一个节点由二元组\((k,w)\)组成。要求\(k\)满足二叉搜索树的性质,\(w\)满足堆的性质。当\(k,w\)都确定,且\(k,w\)互不相同时,笛卡尔树的结构是唯一的,如图:看到这个定义,会发现与Treap十分相似。实际上,Treap就是一种特殊的笛卡尔树。通......
  • P7219 [JOISC2020] 星座 3【笛卡尔树+整体dp】
    P7219[JOISC2020]星座3笛卡尔树+整体dp(线段树合并维护dp)考虑转化题意,不存在矩形为星座,即对于每个极大矩形中都只有一颗星星。而观察题目的方格,对于两个位置是否能够成为一个矩形,只和两个位置的区间最大值(小白船的位置)有关①。图中的红蓝矩形即为两个极大矩形。将删除星......
  • P1377 [TJOI2011] 树的序 (笛卡尔树)
    笛卡尔树模板题题目给出一个生成序列要我们构造一个二叉搜索树。所以值要满足二叉搜索树的性质。因为给出的是生成序列,所以序列的下标是满足最小堆的性质。那么可以按照满足二叉搜索树的那一维度进行排序也就是值进行排序。然后进行构建即可。最后进行先序遍历即可获得答......
  • 笛卡尔树学习笔记
    笛卡尔树学习笔记定义笛卡尔树是一棵特殊的二叉树,它的每个节点都包含了两个值\((k,w)\)。其中,整棵树关于\(k\)为一棵二叉搜索树,而关于\(w\)为一个小根堆(或大根堆)。到这里可以发现,Treap是一种特殊的笛卡尔树,因为Treap相当于给定了\(k\),而我们人为将其随机了一个\(w\)......
  • 笛卡尔乘积
    SQL中的笛卡尔积SQL中的笛卡尔积是数学集合论中的一个术语。但是,我们也可以在SQL数据库手册中找到这个术语。它意味着什么,我们应该如何使用它?让我们来学习一下。两个集合X和Y的笛卡尔积,表示为X×Y,是所有有序对的集合,其中x在X中,y在Y中。就SQL而言,笛卡尔积是......
  • 编程语言中,差、交、并、自然连接、选择、投影、笛卡尔积分别都是什么运算...
    原文:https://blog.csdn.net/muzihuaner/article/details/119529646交(Intersection):关系R与关系S的交由既属于R又属于S的元组组成,即R与S中相同的元组,组成一个新关系,其结果仍为n目关系。记作:R∩S={t|t∈R∧t∈S}简单来说,运算结果就是两或多个实体集所共有的部分 并(Union):......
  • 笛卡尔树学习笔记
    1.定义笛卡尔树是一种特殊的二叉树,同时满足小根堆和二叉搜索树的性质,笛卡尔树的每个节点有两个值(k,w),k满足二叉搜索树性质,w满足小根堆性质。Treap也是一种笛卡尔树2.性质如果k,w是分别两两不同的,那么笛卡尔树也是唯一的对于一颗笛卡尔树,它的中序遍历是原序列a在原序列中......
  • 笛卡尔树
    笛卡尔树定义以一个数列为基础,存储数列中元素,满足两个限制的树。一是数列中元素的下标满足二叉搜索树的性质,二是元素的大小满足堆的性质。建树使用单调栈,在线建树。考虑从左往右在已有的笛卡尔树中添加元素,因为新元素的下标最大,所以只可能取代最右链中的某个元素,并将其收为左......