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

笛卡尔树

时间:2024-07-04 16:44:55浏览次数:14  
标签:笛卡尔 int top cin stk --

笛卡尔树

对于每个区间, 找到区间的极值, 把这个区间一分为二, 这个极值就是这个区间的根, 两个部分的根是极值的两个儿子

如何求笛卡尔树 ?

以大根堆为例

方法一

令 \(l_i\) 表示第 \(i\) 个元素向左第一个 \(\ge\) 它的位置, \(r_i\) 表示第 \(i\) 个元素向右第一个 \(\ge\) 它的位置

其中 \(a_{l_i}\) 和 \(a_{r_i}\) 较小的是当前点的父亲

较大的一个肯定不是它的父亲, 儿子起码是另一边的。

到较小的一个做根时, 肯定不会包含较大的, 我们有知道 \(i\) 就是 \([l_i + 1, r_i - 1]\) 中最大的

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

int n, l[N], r[N], top, stk[N], a[N];

int main(){
  cin >> n;
  a[0] = -1, a[n + 1] = -1;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }
  top = 0;
  for(int i = 1; i <= n + 1; ++i){
    for(; top && a[stk[top]] > a[i]; r[stk[top--]] = i){
    }
    stk[++top] = i;
  }
  top = 0;
  for(int i = n; ~i; i--){
    for(; top && a[stk[top]] > a[i]; l[stk[top--]] = i){
    }
    stk[++top] = i;
  }
  return 0;
}

方法二

考虑对数组做一遍单调栈, 栈内依次递减, 所有最后一个被挤出去的就是左儿子, 被挤出去时右边的就是右儿子

#include<bits/stdc++.h>

using namespace std;

const int N = 1e7 + 5;

int n, last, l[N], r[N], stk[N], top, a[N];
long long lcnt, rcnt;

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }
  for(int i = 1; i <= n; ++i){
    for(last = 0; top && a[stk[top]] > a[i]; last = stk[top--]){
    }
    l[i] = last;
    if(top){
      r[stk[top]] = i;
    }
    stk[++top] = i;
  }
  return 0;
}

标签:笛卡尔,int,top,cin,stk,--
From: https://www.cnblogs.com/liuyichen0401/p/18283695

相关文章

  • 笛卡尔树
    引入首先我们看到这个序列\([9,4,10,1,7,2,3]\),现在我们找到它的最大值\(10\),并从中间劈开,此时分为了两个序列\([9,4]\)和\([1,7,2,3]\),接着对这两个序列继续这样的操作。现在,将劈开后序列最大值和被劈开的数建立父子关系,于是便建立了这个树:这也就是笛卡尔树。笛卡尔树满......
  • 基环树和笛卡尔树
    基环树就是比平常的树多一条边,有\(n\)条边,也就有一个环在里面。基本思想就是断环,跑树形\(dp\),或者用拓扑排序判环去跑环形\(dp\)。树的直径今天才了解到的,用两遍\(dfs\)跑。首先第一遍找到离根节点最远的节点\(u_1\),然后再从\(u_1\)找到离它最远的节点\(u_2\),那么......
  • 基环树和笛卡尔树
    1.基环树定义:有\(n\)个点和\(n\)条边的图,就是给树连了一条边,此时图中恰好只有一个环解决这类问题时,通常断环,变成普通的树的问题,然后再特殊处理环P2607[ZJOI2008]骑士click断环成树后就跟没上司一样是个树形dp,注意森林,longlong就行了,具体细节见这里P5022[NOIP2018提高组......
  • 过滤条件之分组 group by、having、distinct、order by、limit、正则、多表查询和子查
    【一】过滤条件之分组groupby【1】引入--按照指定条件对所有数据进行分组--对员工进行分组按照年龄/部门--...select*from*where*groupby*;【2】按照部门分组(1)查询数据select*fromempgroupbypost;#第一次使用部门分组会报错mysql>select*f......
  • 笛卡尔树
    笛卡尔树引入笛卡尔树是一种二叉树,每一个节点由一个键值二元组\((k,w)\)构成。要求k满足二叉搜索树的性质,而w满足堆的性质。一个有趣的事实是,如果笛卡尔树的\(k,w\)键值确定,且k互不相同,w互不相同,那么这个笛卡尔树的结构是唯一的。上面这棵笛卡尔树相当于把数组元素当作键值w,......
  • 赛克oj The diameter of a rectangle(笛卡尔树)
    赛氪OJ-专注于算法竞赛的在线评测系统(saikr.com)这题是hduoj1506的加强版,区别在于宽度不是固定为1了,思路差不多,也是使用笛卡尔树。参考hduoj1506(笛卡尔树)-Venux-博客园(cnblogs.com)1#defineIOstd::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)2#definebu......
  • hduoj 1506(笛卡尔树)
    Problem-1506(hdu.edu.cn)题意坐标轴给定一些矩形,紧密排在一起,每个矩形宽度固定为1,问形成的图案中最大可以组成的矩形面积。思路常规思路是可以用单调栈分别找两边的合法边界,这里使用笛卡尔树。笛卡尔树实现了堆的性质,并且对原数组建立的笛卡尔树进行中序遍历为原数组的顺......
  • [NOI2009] 二叉查找树 & 笛卡尔树学习笔记
    这个题:二叉搜索树原理认识+区间dp;只要熟练相关算法就一定可以做出来。但我不行。。。我们学习一下笛卡尔树:什么垃圾东西,不学了。发现这个题是l蓝书上一道题jqb。二叉查找树又有一个性质:二叉查找树的中序遍历是其代表的序列从小到大排序的结果。而无论Treap如何旋转,其都......
  • 笛卡尔树学习笔记
    笛卡尔树引入是一种二叉树,每个节点由一个二元组\((k,w)\)形成。\(k\)满足二叉搜索树的性质,\(w\)满足堆的性质。上面这棵笛卡尔树相当于把数组元素值当作键值\(w\),而把数组下标当作键值\(k\)。显然可以发现,这棵树的键值\(k\)满足二叉搜索树的性质,而键值\(w\)满足小根......
  • 生成带重复的笛卡尔乘积过程 Cartesian Product with Repetition
    目录WhatisCartesianProductwithRepetitionCodeDemoWhatisCartesianProductwithRepetition比如说有两个集合:\(\{1,2,3\}\)\(\{A,B,C\}\)想把他们组合成所有可能组合,比如,1AAA1AAB1AAC...这种组合可以称为"有重复的笛卡尔积"或"带重复的笛卡尔乘积"(Carte......