笛卡尔树

笛卡尔树

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

如何求笛卡尔树 ?

以大根堆为例

方法一

令 \(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;
}