HDU - 6305 RMQ Similar Sequence(笛卡尔树)

时间:2022-10-31 12:21:38

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同构的概率为HDU - 6305 RMQ Similar Sequence(笛卡尔树),因为B中的数满足均匀分布(因为B中的元素为[0,1]中的任意实数),所以每个位置的期望值为(0+1)/2,那么B的重量总和为n/2,所以B的重量的期望值为HDU - 6305 RMQ Similar Sequence(笛卡尔树)

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

#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(笛卡尔树)的更多相关文章

  1. hdu 6305 RMQ Similar Sequence——概率方面的思路&plus;笛卡尔树

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=6305 看题解,得知: 0~1内随机取实数,取到两个相同的数的概率是0,所以认为 b 序列是一个排列. 两个 ...

  2. HDU 6305&period;RMQ Similar Sequence-笛卡尔树&plus;数学期望 &lpar;2018 Multi-University Training Contest 1 1008&rpar;

    6305.RMQ Similar Sequence 这个题的意思就是对于A,B两个序列,任意的l,r,如果RMQ(A,l,r)=RMQ(B,l,r),B序列里的数为[0,1]的实数,B的重量为B的所有 ...

  3. &lbrack;乱搞&rsqb;hdu 6406 Taotao picks apples 笛卡尔树&plus;倍增

    题目链接 Problem Description There is an apple tree in front of Taotao's house. When autumn comes, n app ...

  4. 2018 Multi-University Training Contest 1 H - RMQ Similar Sequence(HDU - 6305 笛卡尔树)

    题意: 对于一个序列a,构造一个序列b,使得两个序列,对于任意的区间 [l, r] 的区间最靠近左端点的那个最大值的位置,并且序列 b 满足 0 < bi < 1. 给定一个序列 a ,求 ...

  5. &lbrack;模板&rsqb; 笛卡尔树 &amp&semi;&amp&semi; RMQ

    话说我noip之前为什么要学这种东西... 简介 笛卡尔树(Cartesian Tree) 是一种二叉树, 且同时具有以下两种性质: 父亲节点的值大于/小于子节点的值; 中序遍历的结果为原序列. 笛卡 ...

  6. hdu 1506 Largest Rectangle in a Histogram——笛卡尔树

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=1506 关于笛卡尔树的构建:https://www.cnblogs.com/reverymoon/p/952 ...

  7. HDU - 1506 Largest Rectangle in a Histogram &lpar;单调栈&sol;笛卡尔树&rpar;

    题意:求一个直方图中最大矩形的面积. 很经典的一道问题了吧,可以用单调栈分别求出每个柱子左右两边第一个比它低的柱子(也就相当于求出了和它相连的最后一个比它高的柱子),确定每个柱子的左右边界,每个柱子的 ...

  8. 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 ...

  9. 笛卡尔树--牛客第四场(sequence)

    思路: O(n)建一颗笛卡尔树,再O(n)dfs向上合并答案就行了. #define IOS ios_base::sync_with_stdio(0); cin.tie(0); #include &l ...

随机推荐

  1. 基于HttpModule的简单&period;NET网站授权方案

    摘要 本文介绍一种入门级的网站授权(注:这里所指的授权指的是注册码效果,而不是网站登陆时的身份授权)方案,仅供学习交流及对付小白客户使用.复杂的网站授权涉及网站加密等一系列复杂的技术,不做本文介绍内容 ...

  2. 2015 WEB前端学习路线图

    2015 WEB前端学习路线图,欢迎小伙伴补充 @落雨

  3. Android 开发中使用Intent传递数据的方法

    Activity之间通过Intent传递值,支持基本数据类型和String对象及 它们的数组对象byte.byte[].char.char[].boolean.boolean[].short.shor ...

  4. matlab GUI之自定义菜单小结

    自定义菜单 1.uimenu对象 h=uimenu('PropertyName','ProperValue') h=uimenu(parent,'PropertyName','ProperValue' ...

  5. Oracle第一天

    Oracle第一天 v3.1 整体安排(3天) 第一天:Oracle的安装配置(服务端和客户端),SQL增强(单表查询). 第二天:SQL增强(多表查询.子查询.伪列-分页),数据库对象(表.约束.序 ...

  6. 使用 Http 的 Post 方式与网络交互通信

    package zw1; import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStream; ...

  7. SpringBoot进阶教程&lpar;二十八&rpar;整合Redis事物

    Redis默认情况下,事务支持被禁用,必须通过设置setEnableTransactionSupport(true)为使用中的每个redistplate显式启用.这样做会强制将当前重新连接绑定到触发m ...

  8. Mac下配置多个SSH KEY访问远程Git服务

    第一步 生成对应的ssh key 1 后面输入你的用户名 或者 邮箱 2 输入一个独立的ssh key名字 区别之前的名字 第二步  编辑 config文件 在.ssh/目录下面 在config文件配 ...

  9. 微信小程序开发学习资料

    作者:初雪链接:https://www.zhihu.com/question/50907897/answer/128494332来源:知乎著作权归作者所有.商业转载请联系作者获得授权,非商业转载请注明 ...

  10. 剑指offer3

    输入一个链表,从尾到头打印链表每个节点的值. 思路:首先借助一个栈,遍历链表中的每一个值,然后存储到栈中,利用栈的先进后出特点,然后添加到数组中返回. package demo3; import ja ...