hdu 6305 RMQ Similar Sequence
题意：定义两个序列相似：对于任意的 l<=r，A序列区间[ l , r ]的最值下标 = B序列区间[ l , r ]的最值下标，现给出A序列，已知B序列元素为[0,1]之间的实数，求与A相似的B序列的所有元素期望和。
思路借鉴：丿残念灬
模板借鉴：qkoqhh
笛卡尔树简介：笛卡尔树
思路：知道了笛卡尔树特性后，这题可以转化求与A的笛卡尔树的同构树方案，对于大小为sz[u]的子树rt[u]，因为最大的数必须为根，很显然其同构方案的概率为1/sz[u]，因此B元素完全随机与A的笛卡尔树同构的概率为，每个元素期望的值为1/2，因此答案为：概率*n/2。
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=1e6+10,mod=1e9+7; int a[maxn],l[maxn],r[maxn],sz[maxn],inv[maxn]; ll ans; stack<int>s; void dfs(int u) { sz[u]=1; if(l[u]) dfs(l[u]),sz[u]+=sz[l[u]]; if(r[u]) dfs(r[u]),sz[u]+=sz[r[u]]; ans=ans*inv[sz[u]]%mod; } int main() { int T; inv[0]=inv[1]=1; for(int i=2;i<=1000000;i++) inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod; scanf("%d",&T); while(T--) { int n,rt; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); l[i]=r[i]=0; while(!s.empty()&&a[i]>a[s.top()]) l[i]=s.top(),s.pop(); if(!s.empty()) r[s.top()]=i; s.push(i); } while(!s.empty()) rt=s.top(),s.pop(); ans=1ll*n*inv[2]%mod; dfs(rt); printf("%lld\n",ans); } }
