2018 Multi-1 H - RMQ Similar Sequence

#题目链接

#题意简述

定义RMQ(A,l,r)为：序列A中，满足A[i] = max(A[l],A[l+1],…,A[r])的最大的i。如果对于任意(l,r)都满足RMQ(A,l,r)=RMQ(B,l,r)则为A和B是RMQ Similar。现在出A序列，B串中每个元素服从于[0,1]上相互独立的均匀分布。问满足与A是RMQ Similar的所有B序列中所有数之和的期望。(转载)

#简要做法

要解决这个问题，首先需要学习一下笛卡尔树。

我们用数组A的下标作为key值，数组元素值作为value构建笛卡尔树。

这样的笛卡尔树的性质是：

每个节点的子树有大/小根堆的性质
每个节点的子树的key值构成一个连续区间
每个节点的key值符合二叉搜索树的性质

本题和头两个性质有密切关系。从性质可以看出，如果两个数组RMQ Similar，那么它们构成的笛卡尔树同构。

因此我们用数组A构建笛卡尔树，来计算B的树与A的树同构的概率。

由于构建起来的是笛卡尔树，由性质1，可知对于每个节点，其作为子树根节点时，是区间RMQ的概率应该为子树的大小分之一。即$\frac{1}{size[t]}$。

对于不同的节点，这样的概率是独立的。所以总体概率为：
$$
\prod_{i=1}^n \frac{1}{size[i]}
$$
由于每一个点的权值服从[0,1]的均匀分布，所以权值的期望是n/2。

故答案为：
$$
\frac{n}{2}\prod_{i=1}^n \frac{1}{size[i]}
$$

#参考代码

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

const int maxn = 1e6 + 5;

int n, a[maxn], ans;

int st[maxn], top;

int ls[maxn], rs[maxn];

ll inv[maxn];

int dfs(int u) {

    int s = 1;

    if(ls[u])

        s += dfs(ls[u]);

    if(rs[u])

        s += dfs(rs[u]);

    ans = ans * inv[s] % mod;

    return s;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr), cout.tie(nullptr);

    int t;

    cin >> t;

    inv[1] = 1;

    for(int i = 2; i <= 1000000; ++i)

        inv[i] = inv[mod % i] * (mod - mod / i) % mod; // 处理逆元

    while(t--) {

        cin >> n;

        for(int i = 1; i <= n; ++i) cin >> a[i];

        top = 0;

        for(int i = 1; i <= n; ++i) ls[i] = rs[i] = 0;

        for(int i = 1; i <= n; ++i) { //构建笛卡尔树

            int k = top;

            while(k && a[st[k]] < a[i]) k--;

            if(k) rs[st[k]] = i;

            if(k < top) ls[i] = st[k + 1];

            st[++k] = i, top = k;

        ans = n * inv[2] % mod;

        dfs(st[1]); // dfs处理子树数量

        cout << ans << '\n';

    return 0;