笛卡尔树

笛卡尔树

性质：

1.区间最小值（RMQ)等于左右端点lca的值

2.中序遍历就是原数组

用处：

给定一段区间，求$\sum_{i=1}^{n}\sum_{j=1}^{n}min(a_i \dots a_j)$，转化成树上问题

int a[N], l[N], r[N];
void build() {
    stack<int> st;
    int root = 0;
    for (int i = 1; i <= n; i++) {
        int last = 0;
        while (!st.empty() && a[st.top()] > a[i]) {
            last = st.top();
            st.pop();
        }
        if (!st.empty())
            r[st.top()] = i;
        else
            root = i;
        l[i] = last;
        st.push(i);
    }
}