笛卡尔树是一种二叉树，每个节点 \(i\) 由 \(\left(k_i,w_i\right)\) 构成， 其中，\(k\) 满足BST 的性质，\(w\) 满足堆的性质。
-
若 \(k,w\) 互不相同，则构成的笛卡尔树唯一；
-
两个点的 \(LCA\) 即它们的 \(RMQ\)。
构建一颗笛卡尔树，先以 \(k\) 为序排序，再维护一条右链。（@虚树）
\(\textrm{luogu P5854 【模板】笛卡尔树}\)
#include <stdio.h>
#define llt long long int
const int N = 1e7+10;
int n, p[N];
int stk[N], top;
int rid[N], lid[N];
llt lans, rans;
void cts() {
for(int i = 1, k = 0;i <= n;++i) {
while(k&&p[stk[k]] > p[i])
--k;
if(k)
rid[stk[k]] = i;
if(k < top)
lid[i] = stk[k+1];
stk[++k] = i;
top = k;
}
}
signed main() {
get_int(n);
for(int i = 1;i <= n;++i)
get_int(p[i]);
cts();
for(int i = 1;i <= n;++i) {
lans ^= i*(lid[i]+1LL);
rans ^= i*(rid[i]+1LL);
}
printf("%lld %lld\n",lans,rans);
return 0;
}
ps:本题卡常，请使用较快的读入方式
标签：笛卡尔,int,top,stk,llt,模板 From： https://www.cnblogs.com/bikuhiku/p/Descartes_tree.html