CF1748E Yet Another Array Counting Problem

CF1748E Yet Another Array Counting Problem

yzxoi

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

oi ST, dp, 二分

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

• 序列 b 长度为 n，且对任意整数 i(1\leq i\leq n) 都有 1\leq b_i\leq m 成立。
• 对任意整数 l,r(1\leq l\leq r\leq n)，总有 a,b 在子段 [l;r] 的“最左端最大值位置”相同。

答案对 10^9+7 取模。

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

Tutorial

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

，有：

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

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

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

容易有转移：

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

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