笛卡尔树
O(n)建立一颗该节点是当前子树的最值的二叉树.
代码:
void Build(){ int n; scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), L[i] = R[i] = 0; top = 0; for(int i = 1; i <= n; ++i){ while(top && a[sta[top]] > a[i]) L[i] = sta[top--]; if(top) R[sta[top]] = i; sta[++top] = i; } }
原文：https://www.cnblogs.com/MingSD/p/11260795.html
