http://acm.hdu.edu.cn/showproblem.php?pid=6305
题目
对于A,B两个序列,任意的l,r,如果RMQ(A,l,r)=RMQ(B,l,r),B序列里的数为[0,1]的实数,B的重量为B的所有元素的和,否则为0。问你B的期望重量是多少。
分析
准备知识:笛卡尔树https://skywt.cn/posts/cartesian-tree/
RMQ-Similar实际上就是A和B的笛卡尔树一样。于是这个题就是笛卡尔树同构的问题,假设A的笛卡尔树的子树大小为sz[u],那么序列B与A同构的概率为,因为B中的数满足均匀分布(因为B中的元素为[0,1]中的任意实数),所以每个位置的期望值为(0+1)/2,那么B的重量总和为n/2,所以B的重量的期望值为。
实际上对这题我还没完全懂,暂且记录一下吧。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cassert>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;
const int maxn=1e6+;
const int inf=0x3f3f3f3f;
const int mod=1e9+; stack<int>st;
ll inv[maxn];
int n; struct node{
int val,sz;
int l,r,par;
}t[maxn]; void init()
{
for(int i=;i<=n;i++)
t[i].l=,t[i].r=,t[i].par=,t[i].sz=;//初始化
t[].val=inf;
while(!st.empty())
st.pop();
st.push();
} void build()
{
for(int i=;i<=n;i++){
while(!st.empty()&&t[st.top()].val<t[i].val)//从栈顶往栈底遍历,
st.pop();
int par=st.top();
t[i].par=par;//i.par为st.pop()
t[i].l=t[par].r;
t[t[par].r].par=i;
t[par].r=i;//右子树
st.push(i);
}
} void dfs(int u)
{
if(u==) return ;
t[u].sz=;
dfs(t[u].l);
dfs(t[u].r);
t[u].sz+=t[t[u].l].sz+t[t[u].r].sz;
} void Inv(){//扩展gcd求逆元
inv[]=;
for(int i=;i<maxn;i++)
inv[i]=inv[mod%i]*(mod-mod/i)%mod;
} int main()
{
int T;
Inv();
scanf("%d",&T);
while(T--){
scanf("%d",&n);
init();
for(int i=;i<=n;i++)
scanf("%d",&t[i].val);
build();
dfs(t[].r); ll ans=n*inv[]%mod;
for(int i=;i<=n;i++)
ans=ans*inv[t[i].sz]%mod;
printf("%lld\n",ans);
}
}
HDU - 6305 RMQ Similar Sequence(笛卡尔树)的更多相关文章
-
hdu 6305 RMQ Similar Sequence——概率方面的思路+笛卡尔树
题目:http://acm.hdu.edu.cn/showproblem.php?pid=6305 看题解,得知: 0~1内随机取实数,取到两个相同的数的概率是0,所以认为 b 序列是一个排列. 两个 ...
-
HDU 6305.RMQ Similar Sequence-笛卡尔树+数学期望 (2018 Multi-University Training Contest 1 1008)
6305.RMQ Similar Sequence 这个题的意思就是对于A,B两个序列,任意的l,r,如果RMQ(A,l,r)=RMQ(B,l,r),B序列里的数为[0,1]的实数,B的重量为B的所有 ...
-
[乱搞]hdu 6406 Taotao picks apples 笛卡尔树+倍增
题目链接 Problem Description There is an apple tree in front of Taotao's house. When autumn comes, n app ...
-
2018 Multi-University Training Contest 1 H - RMQ Similar Sequence(HDU - 6305 笛卡尔树)
题意: 对于一个序列a,构造一个序列b,使得两个序列,对于任意的区间 [l, r] 的区间最靠近左端点的那个最大值的位置,并且序列 b 满足 0 < bi < 1. 给定一个序列 a ,求 ...
-
[模板] 笛卡尔树 &;&; RMQ
话说我noip之前为什么要学这种东西... 简介 笛卡尔树(Cartesian Tree) 是一种二叉树, 且同时具有以下两种性质: 父亲节点的值大于/小于子节点的值; 中序遍历的结果为原序列. 笛卡 ...
-
hdu 1506 Largest Rectangle in a Histogram——笛卡尔树
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1506 关于笛卡尔树的构建:https://www.cnblogs.com/reverymoon/p/952 ...
-
HDU - 1506 Largest Rectangle in a Histogram (单调栈/笛卡尔树)
题意:求一个直方图中最大矩形的面积. 很经典的一道问题了吧,可以用单调栈分别求出每个柱子左右两边第一个比它低的柱子(也就相当于求出了和它相连的最后一个比它高的柱子),确定每个柱子的左右边界,每个柱子的 ...
-
HDU 1506 Largest Rectangle in a Histogram(单调栈、笛卡尔树)
题意:给定n个连续排列的矩形的高,矩形的宽都为1.问最大矩形覆盖. 例如:n = 7,h[i] = (2 1 4 5 1 3 3),最大覆盖为8. Sample Input 7 2 1 4 5 1 3 ...
-
笛卡尔树--牛客第四场(sequence)
思路: O(n)建一颗笛卡尔树,再O(n)dfs向上合并答案就行了. #define IOS ios_base::sync_with_stdio(0); cin.tie(0); #include &l ...
随机推荐
-
基于HttpModule的简单.NET网站授权方案
摘要 本文介绍一种入门级的网站授权(注:这里所指的授权指的是注册码效果,而不是网站登陆时的身份授权)方案,仅供学习交流及对付小白客户使用.复杂的网站授权涉及网站加密等一系列复杂的技术,不做本文介绍内容 ...
-
2015 WEB前端学习路线图
2015 WEB前端学习路线图,欢迎小伙伴补充 @落雨
-
Android 开发中使用Intent传递数据的方法
Activity之间通过Intent传递值,支持基本数据类型和String对象及 它们的数组对象byte.byte[].char.char[].boolean.boolean[].short.shor ...
-
matlab GUI之自定义菜单小结
自定义菜单 1.uimenu对象 h=uimenu('PropertyName','ProperValue') h=uimenu(parent,'PropertyName','ProperValue' ...
-
Oracle第一天
Oracle第一天 v3.1 整体安排(3天) 第一天:Oracle的安装配置(服务端和客户端),SQL增强(单表查询). 第二天:SQL增强(多表查询.子查询.伪列-分页),数据库对象(表.约束.序 ...
-
使用 Http 的 Post 方式与网络交互通信
package zw1; import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStream; ...
-
SpringBoot进阶教程(二十八)整合Redis事物
Redis默认情况下,事务支持被禁用,必须通过设置setEnableTransactionSupport(true)为使用中的每个redistplate显式启用.这样做会强制将当前重新连接绑定到触发m ...
-
Mac下配置多个SSH KEY访问远程Git服务
第一步 生成对应的ssh key 1 后面输入你的用户名 或者 邮箱 2 输入一个独立的ssh key名字 区别之前的名字 第二步 编辑 config文件 在.ssh/目录下面 在config文件配 ...
-
微信小程序开发学习资料
作者:初雪链接:https://www.zhihu.com/question/50907897/answer/128494332来源:知乎著作权归作者所有.商业转载请联系作者获得授权,非商业转载请注明 ...
-
剑指offer3
输入一个链表,从尾到头打印链表每个节点的值. 思路:首先借助一个栈,遍历链表中的每一个值,然后存储到栈中,利用栈的先进后出特点,然后添加到数组中返回. package demo3; import ja ...