CF1748E Yet Another Array Counting Problem
对于长度为 $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}$。
对于区间 $[i,j]$，设 $m=f_{i,j}$，$p_1=f_{i,m-1}$，$p_2=f_{m+1,j}$，有：
$$
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)$。