hdu 6305 RMQ Similar Sequence（笛卡尔树模板）

深碍√TFBOYSˉ_ 2021-12-04 00:03 298阅读 0赞

## 题意：   设RMQ（A，l，r）为最小的 i ，使得a\[i\]是a\[l\]-a\[r\]中的最大值。若A、B两个数组RMQ相似，则A、B等长，且在1<=l<=r<=n内，RMQ(A,l,r)=RMQ(B,l,r)。现在A数组已知，B数组在\[0,1\]均匀分布，设B数组的权重为数组内各元素的和。若A与B相似，求B权重的期望。 ##

## 题解：   RMQ-Similar实际上就是 A和 B的笛卡尔树一样（同构），这样我们就有了一个二叉树，然后可以在树上分析了。考虑到B中有元素相同的概率是 0，于是可以假设 B里面元素互不相同，也就是说可以假定是一个排列。显然，符合笛卡尔树的排列就是这个树的拓扑序列个数，就是![aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTA5NjE2OS8yMDE4MDcvMTA5NjE2OS0yMDE4MDczMTEyNTUyMzg5MS0yMTQyNzg1OTE0LnBuZw][]。然后显然每个排列期望的和是，于是答案就是![\\frac\{n\}\{2\\prod size\[i\]\}][frac_n_2_prod size_i] 。 ##

## 笛卡尔树的性质：   1.树中的元素满足二叉搜索树性质，要求按照中序遍历得到的序列为原数组序列(左儿子的key值小于自己，右儿子的key值大于自己)。 ##

## 2.树中节点满足堆性质，节点的val值要大于其左右子节点的val值。 ##

# 判断树同构 ： 最小表示法   树是DAG（有向无环图）的一种，    求n个点的树的拓扑序列的个数？    考虑1~n的全排列,有n！个排列    设A子树的大小为size\[A\]    对于每个节点A , A在拓扑序列中要在其子树中所有其他点的后面，于是我们只考虑A的子树中的点的排列，发现只有1/size\[A\]的排列是符合上述要求的，又每个点的要求之间都无关（要求只是对当前点有关），所以符合所有要求的排列为![aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTA5NjE2OS8yMDE4MDcvMTA5NjE2OS0yMDE4MDczMTEyNTUyMzg5MS0yMTQyNzg1OTE0LnBuZw][]。 #

## 参考：[https://blog.csdn.net/luyehao1/article/details/81280093][https_blog.csdn.net_luyehao1_article_details_81280093]、 ##

## [https://blog.csdn.net/qq\_35950004/article/details/81356898][https_blog.csdn.net_qq_35950004_article_details_81356898]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1e6+10;
    const ll mod = 1e9+7;
    
    int n, l[N], r[N], vis[N], stk[N], inv[N], siz[N];
    ll a[N];
    
    ///建笛卡尔树模板，返回的是树的根节点下标
    int build() {
        int top = 0;
        for(int i=1;i<=n;i++) l[i] = r[i] = vis[i] = 0;
        for(int i=1;i<=n;i++){
            int k = top;
            while(k > 0 && a[stk[k - 1]] < a[i]) --k;
            if(k) r[stk[k-1]] = i;
            if(k<top) l[i] = stk[k];
            stk[k++] = i;
            top = k;
        }
        for(int i=1;i<=n;i++) vis[l[i]] = vis[r[i]] = 1;
        int ret = 0;
        for(int i=1;i<=n;i++) if(vis[i] == 0) ret = i;
        return ret;
    }
    
    void dfs(int root){
        siz[root]=1;
        if(l[root]){
            dfs(l[root]);
            siz[root]+=siz[l[root]];
        }
        if(r[root]){
            dfs(r[root]);
            siz[root]+=siz[r[root]];
        }
    }
    
    int main(){
        int T;
        scanf("%d",&T);
        //求逆元模板
        inv[1]=1;
        for(int i=2;i<N;i++)
            inv[i] = 1LL * inv[mod%i]*(mod-mod/i)%mod;
        while(T--){
            scanf("%d",&n);
            for(int i=1;i<=n;i++)
                scanf("%lld",&a[i]);
            int root=build();
            for(int i=0;i<=n;i++) siz[i]=0;
            dfs(root);
            ll ans=1;
            for(int i=1;i<=n;i++) ans=ans*inv[siz[i]]%mod;
            ans=(ans*n)%mod*inv[2]%mod;
            printf("%lld\n",ans);
        }
        return 0;
    }

[aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTA5NjE2OS8yMDE4MDcvMTA5NjE2OS0yMDE4MDczMTEyNTUyMzg5MS0yMTQyNzg1OTE0LnBuZw]: /images/20211203/c2df4c933ebe4847a1cb9d1d18829024.png
[frac_n_2_prod size_i]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9wcml2YXRlLmNvZGVjb2dzLmNvbS9naWYubGF0ZXg_JTVDZnJhYyU3Qm4lN0QlN0IyJTVDcHJvZCUyMHNpemUlNUJpJTVEJTdE
[https_blog.csdn.net_luyehao1_article_details_81280093]: https://blog.csdn.net/luyehao1/article/details/81280093
[https_blog.csdn.net_qq_35950004_article_details_81356898]: https://blog.csdn.net/qq_35950004/article/details/81356898