2018 Multi-University Training Contest 1 H - RMQ Similar Sequence（HDU - 6305 笛卡尔树）

题意：

对于一个序列a，构造一个序列b，使得两个序列，对于任意的区间 [l, r] 的区间最靠近左端点的那个最大值的位置，并且序列 b 满足 0 < bi < 1。

给定一个序列 a ,求序列 b 中所有元素的和的期望。

Sample Input

3

3

1 2 3

3

1 2 1

5

1 2 3 2 1

Sample Output

250000002

500000004

125000001

题解：

若满足题意，则 a 和 b 的笛卡尔树同构。

因为 bi 在 0 到 1 之间，故 bi 的期望值为 1/2 ，所以 b 序列的和的期望值为 n/2。
对于笛卡尔树的每一棵子树，若用sz[i]表示以 i 为根节点的子树的大小，则满足其根节点是子树的最大值的概率为 1/sz[i] 。

所以整棵树满足条件的概率为1 / Πsz[i]。

故总期望值为两个的乘积 n / 2Πsz[i]。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <stack>

using namespace std;

typedef long long LL;

const int maxn = ;

const int MOD = 1e9+;

int a[maxn], lson[maxn], rson[maxn], fa[maxn];

LL dp[maxn], inv[maxn];

LL tmp;

LL DP(int id)

{

    if (id == ) return ;

    if (dp[id]) return dp[id];

    dp[id] = DP(lson[id]) + DP(rson[id]) + ;

    return dp[id];

}

void getinv()

{

    inv[] = ;

    for (int i = ; i < maxn; i++)

        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;

}

int main()

{

    int t, n;

    scanf("%d", &t);

    getinv();

    for (int ca = ; ca <= t; ca++)

    {

        scanf("%d", &n);

        for (int i = ; i <= n; i++) scanf("%d", &a[i]);

        stack<int> st;

        for (int i = ; i <= n; i++)

            lson[i] = rson[i] = fa[i] = dp[i] = ;

        for (int i = ; i <= n; i++)

        {

            if (!st.empty() && a[st.top()] < a[i])

            {

                while (!st.empty() && a[st.top()] < a[i])

                    tmp = st.top(), st.pop();

                lson[i] = tmp, fa[tmp] = i;

            }

            if (!st.empty()) rson[st.top()] = i, fa[i] = st.top();

            st.push(i);

        }

        for (int i = ; i <= n; i++) if (!fa[i]) DP(i);

        LL ans = n * inv[] % MOD;

        for (int i = ; i <= n; i++) ans = ans * inv[dp[i]] % MOD;

        printf("%lld\n", ans);

    }

}