定义

笛卡尔树是一棵二叉树，满足:

1. 每个节点的键值满足二叉搜索树，即中序遍历后严格递增；
2. 每个节点的权值满足小根堆。

建树例题

【模板】笛卡尔树

建树

long long n;
std::vector<long long> p(n+3, 0);
std::vector<long long> l(n+3, 0), r(n+3, 0), stk;
stk.push_back(1); // 栈维护最右链
for(long long i = 2; i <= n; ++i) {
  for(; stk.size() && p[i] < p[stk.back()]; ) {
    long long u = stk.back();
    stk.pop_back();
    r[u] = l[i];
    l[i] = u;
  } // 维持小根堆性质
  if(stk.size()) // 认爹
    r[stk.back()] = i;
  stk.push_back(i);
}