笛卡尔树

        笛卡尔树,一种解决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;
}

0%