题目

 对于A，B两个序列，任意的l，r，如果RMQ(A，l，r)=RMQ(B，l，r)，B序列里的数为[0,1]的实数，B的重量为B的所有元素的和，否则为0。问你B的期望重量是多少。

分析

 准备知识：笛卡尔树

RMQ-Similar实际上就是A和B的笛卡尔树一样。于是这个题就是笛卡尔树同构的问题，假设A的笛卡尔树的子树大小为sz[u]，那么序列B与A同构的概率为，因为B中的数满足均匀分布(因为B中的元素为[0,1]中的任意实数)，所以每个位置的期望值为(0+1)/2，那么B的重量总和为n/2，所以B的重量的期望值为。

实际上对这题我还没完全懂，暂且记录一下吧。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;typedef long long ll;const int maxn=1e6+10;const int inf=0x3f3f3f3f;const int mod=1e9+7;stack
               
                st;ll inv[maxn];int n;struct node{ int val,sz; int l,r,par;}t[maxn];void init(){ for(int i=0;i<=n;i++) t[i].l=0,t[i].r=0,t[i].par=0,t[i].sz=0;//初始化 t[0].val=inf; while(!st.empty()) st.pop(); st.push(0);}void build(){ for(int i=1;i<=n;i++){ while(!st.empty()&&t[st.top()].val