笛卡尔树，一种解决RMQ问题的数据结构。

        笛卡尔树，是一种建立在序列上的特殊的二叉树。笛卡尔树满足以下的特点：

  • 中序遍历序列就是原序列
  • 满足堆性质

        由这两条性质，笛卡尔树非常像Treap，但是Treap的构建复杂度为$O(nlogn)$，笛卡尔树在单调栈的辅助下可以降至$O(n)$。
        关于笛卡尔树的构造算法，我们用小根堆性质为例，算法如下：

  • 现在将第$x$个值加入栈。若栈顶元素值大于$x$对应的值，则弹出栈顶元素$t$，并使$x$的左儿子为$t$。
  • 弹栈完毕后，若栈非空，则栈顶元素的右儿子为$x$。

        算法的正确性可以用数学归纳法证明。
        我们证明，在算法执行过程的每一步后，栈中元素储存的是从根节点一直走右儿子路径的上的节点（即右树链上的节点），显然这些节点的权值是单调上升的，根节点在栈底。
        显然，在第一个元素加入栈后，栈中只有一个元素，符合笛卡尔树定义以及上文定义。
        假设第$k$次操作后符合上述规则，则第$k+1$次时：
        通过弹栈过程，我们找到了右树链上第一个权值小于待加入元素权值的节点$p$，令其为待加入节点的左儿子。此时，若栈空，则待加入节点权值最小，且没有右儿子，剩余部分符合笛卡尔树定义。若栈非空，则此时的栈顶元素为$p$的父节点，将待加入节点作为其右儿子，这显然符合笛卡尔树定义并且符合上述规则。由数学归纳法可知笛卡尔树构造算法是正确的。
        容易发现，在笛卡尔树上，两个节点的lca对应值就是这一段区间的最值，从而可以解决RMQ问题。
        模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#define N 10000000 + 5
using namespace std;
int ch[N][2], v[N], sta[N], top = 0;
inline int read()
{
    char e = getchar();
    int s = 0;
    while (e < '-') e = getchar();
    while (e > '-') s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}
inline void add(int x)
{
    while (top && v[sta[top - 1]] > v[x]) {
        int t = sta[top - 1];
        ch[x][0] = t, --top;
    }
    if (top) ch[sta[top - 1]][1] = x;
    sta[top++] = x;
}
int main()
{
    int n = read();
    for (int i = 1, x; i <= n; i++) v[i] = read(), add(i);
    long long a = 0, b = 0;
    for (int i = 1; i <= n; i++) {
        a ^= 1ll * i * (ch[i][0] + 1);
        b ^= 1ll * i * (ch[i][1] + 1);
    }
    printf("%lld %lld", a, b);
    return 0;
}