笛卡尔树模板

用于 $RMQ$ 问题。

查看代码

#include <cstdio>
using namespace std;
const int N = 1e7 + 10;
struct Node
{
    int l, r, v;
} tr[N];
int n;
int top, stk[N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &tr[i].v);
    for (int i = 1, pos; i <= n; i++)
    {
        pos = top;
        while (pos && tr[stk[pos]].v > tr[i].v)
            pos--;
        if (pos)
            tr[stk[pos]].r = i;
        if (pos < top)
            tr[i].l = stk[pos + 1];
        stk[top = ++pos] = i;
    }
    return 0;
}