HDU 6305 RMQ Similar Sequence——笛卡尔树

题意：

Chiaki has a sequence A={a1,a2,…,an}A={a1,a2,…,an}. Let RMQ(A,l,r)RMQ(A,l,r) be the minimum ii (l≤i≤rl≤i≤r) such that aiai is the maximum value in al,al+1,…,aral,al+1,…,ar.  Two sequences AA and BB are called \textit{RMQ Similar}, if they have the same length nn and for every 1≤l≤r≤n1≤l≤r≤n, RMQ(A,l,r)=RMQ(B,l,r)RMQ(A,l,r)=RMQ(B,l,r).  For a given the sequence A={a1,a2,…,an}A={a1,a2,…,an}, define the weight of a sequence B={b1,b2,…,bn}B={b1,b2,…,bn} be ∑i=1nbi∑i=1nbi (i.e. the sum of all elements in BB) if sequence BB and sequence AA are RMQ Similar, or 00 otherwise. If each element of BB is a real number chosen independently and uniformly at random between 00 and 11, find the expected weight of BB.

思路：

构建序列a的笛卡尔树，随机生成b序列，构建b序列的笛卡尔树，则两笛卡尔树同构的概率为

其中sz【i】表示b的笛卡尔树中以i为根节点的子树的大小（包括i）

b中每个数满足均匀分布，因此期望为

，和的期望为

，因此满足与a同构的b中所有数之和的期望为

#include #include #include #include using namespace std;typedef long long ll;const int maxn = 1e6 + 10;const int mod = 1e9 + 7;int n, a[maxn];int t, st[maxn];int sz;int num[maxn];struct Node { int val, left, right;}node[maxn];void init() { t = sz = 0; for (int i = 0; i <= n; i++) node[i].val = node[i].left = node[i].right = 0; for (int i = 0; i <= n; i++) num[i] = 0;}int build() { int root = 0, pre = 0; for (int i = 1; i <= n; i++) { while (t > 0 && node[st[t]].val < a[i]) pre = st[t--]; node[++sz].val = a[i]; if (t == 0) root = sz; else node[st[t]].right = sz; node[sz].left = pre; st[++t] = sz; pre = 0; } return root;}void dfs(int u) { if (u == 0) return; dfs(node[u].left); dfs(node[u].right); num[u] = num[node[u].left] + num[node[u].right] + 1;}ll ipow(ll x, ll y) { ll ans = 1; while (y) { if (y & 1) ans = ans * x % mod; x = x * x % mod; y >>= 1; } return ans;}void solve() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); init(); dfs(build()); ll ans = n * ipow(2, mod - 2) % mod; for (int i = 1; i <= n; i++) ans = ans * ipow(num[i], mod - 2) % mod; printf("%lld\n", ans);}int main() { int T; scanf("%d", &T); while (T--) { solve(); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。