hdu6305(笛卡尔树+期望)

笛卡尔树

性质

  • 树中的元素满足二叉搜索树性质,要求按照中序遍历得到的序列为原数组序列
  • 树中节点满足堆性质,节点的key值要大于(或小于)其左右子节点的key值
    笛卡尔树与Treap很类似,不同点在于Treap的key值是随机值,而笛卡尔树的key是确定值

笛卡尔树的构建

我们按照Index值(即key值)从小到大插入,因为当前插入元素的Index值总是最大的,所以我们从树的最右边插入(满足二叉搜索树性质)
又要满足堆的性质,所以我们插入一个点A的时候,沿这棵树的最右节点不断向上找,直到找到第一个value值比它大的点B,根据标号,A的左孩子就是B的右孩子(满足二叉搜索),而A就是B的右孩子了(这实际上似乎就是某种旋转)
复杂度分析: 每个节点最多入栈一次,出栈一次,因此时间复杂度为 O(n)

思路

本题中RMQ的结构和序列对应的笛卡尔树是同构的,另key值为数组元素下表,即index,value值为数组元素的值,首先建立笛卡尔树
然后假设满足RMQ结构的方案数为p,[0,1]中随机一个数的期望是1/2,整个序列和为n/2,排列共有n!种
对于一个元素,是当前区间最大值的概率为1/sz(i),sz(i)为以当前元素为根的子树大小,则p = $\frac{n!}{\prod sz_i}$
化简得到最后ans = $\frac{n}{2\prod sz_i}$

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
inline int readint()
{
int res = 0, flag = 0;
char ch;
if((ch = getchar()) == '-')
flag = 1;
else if(ch >= '0' && ch <= '9')
res = ch - '0';
while((ch = getchar()) >= '0' && ch <= '9' )
res = res * 10 + ch - '0';
return flag ? -res : res;
}
const int maxn = 1e6+10;
const ll mod = 1e9+7;
int n;
int pre[maxn] , lson[maxn] , rson[maxn] , st[maxn] , sz[maxn] , inv[maxn];
struct node
{
int key ,value;
int id;
node(){}
node(int kk , int vv ,int ii):key(kk) , value(vv) , id(ii){}
bool operator < (const node &a) const
{
return key < a.key;
}
};
node a[maxn];
void build(int n)
{
int top = 0 , k;
for(int i = 1 ; i <= n ; i ++){
pre[i] = lson[i] = rson[i] = 0;
}
for(int i = 1 ; i <= n ; i ++){
k = top;
while(k && a[st[k]].value < a[i].value) --k;
if(k){
pre[a[i].id] = a[st[k]].id;
rson[a[st[k]].id] = a[i].id;
}
if(k < top){
pre[a[st[k+1]].id] = a[i].id;
lson[a[i].id] = a[st[k+1]].id;
}
st[++k] = i;
top = k;
}
pre[a[st[0]].id] = 0;
}
ll ans;

void init()
{
inv[0] = inv[1] = 1;
for(int i = 2 ; i < maxn ; i++){
inv[i] = (mod - mod / i)*inv[mod % i] % mod;
}
}
void dfs(int u)
{
if(lson[u])dfs(lson[u] );
if(rson[u])dfs(rson[u]);
sz[u] = 1 + sz[lson[u]] + sz[rson[u]];
ans = ( 1LL * (ans) * (ll)inv[sz[u]]) % mod;
}
int main()
{
int T;
scanf("%d" , &T);
init();
while(T--){
scanf("%d" , &n);
int root;
int Max = -1;
for(int i = 1 ; i <= n ; i ++){
scanf("%d" , &a[i].value);
a[i].id = i;
a[i].key = i;
if(a[i].value > Max){
Max = a[i].value;
root = i;
}
}
build(n);
ans = 1;
dfs(root);
printf("%lld\n" , (1LL * ans * n % mod) * (inv[2] % mod) % mod);
}
return 0;
}