CF1748E Yet Another Array Counting Problem
yzxoi
2022-11-14 (Updated: 2022-11-14)
oi ST, dp, 二分
对于长度为 n 的序列 x，定义其在子段 [l;r] 的“最左端最大值位置”为最小的满足 lleq ileq r 且 x_i=max_{j=l}^rx_j 的整数 i。给定整数 n,m 和长度为 n 的序列 a，你需要求出满足下列要求的序列 b 的数量：
- 序列 b 长度为 n，且对任意整数 i(1leq ileq n) 都有 1leq b_ileq m 成立。
- 对任意整数 l,r(1leq lleq rleq n)，总有 a,b 在子段 [l;r] 的“最左端最大值位置”相同。
答案对 10^9 7 取模。
nleq 2times 10^5，ntimes m leq 10^6.
Tutorial
设区间 [l,r] 的最左端最大值位置为 f_{l,r}。
，有：
至此，限制 2 即转换为以上限制。
将一个区间视为一个节点，每个节点则按照如上构造可连出两个子节点，构造一棵二叉树。
设 dp_{u,x} 表示节点 u 对应区间的 m=x 时的方案数。
容易有转移：
对于求最左端最大值位置，ST 表 二分即可。
时间复杂度：O(nlog n)。
