CF1748E Yet Another Array Counting Problem

yzxoi

发布于 2022-11-21 15:52:00

2740

文章被收录于专栏：OIOI

yzxoi

2022-11-14 (Updated: 2022-11-14)

对于长度为 n 的序列 x，定义其在子段 [l;r] 的“最左端最大值位置”为最小的满足 l\leq i\leq r 且 x_i=\max_{j=l}^rx_j 的整数 i。给定整数 n,m 和长度为 n 的序列 a，你需要求出满足下列要求的序列 b 的数量：

答案对 10^9+7 取模。

n\leq 2\times 10^5，n\times m \leq 10^6.

设区间 [l,r] 的最左端最大值位置为 f_{l,r}。

，有：

p_1< m < p_2

b_m > b_{p_1}

b_m \leq b_{p_2}

至此，限制 2 即转换为以上限制。

将一个区间视为一个节点，每个节点则按照如上构造可连出两个子节点，构造一棵二叉树。

设 dp_{u,x} 表示节点 u 对应区间的 m=x 时的方案数。

容易有转移：

dp_{u,x} = (\sum_{i=1}^{x-1} dp_{p_1,i})\cdot (\sum_{i=1}^x dp_{p_2,i})

对于求最左端最大值位置，ST 表+二分即可。

时间复杂度：O(n\log n)。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-11-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度