Yet Another Array Counting Problem
给你一个长度为 \(n\) 的序列和一个数 \(m\)，求有多少个长度为 \(n\) 的序列 \(b\) 满足：
- \(\forall i \in [1, n], b_i \in [1, m]\)。
- 对于每个区间 \([l, r]\)，\(b\) 中最大值最靠左的位置和 \(a\) 相同。
\(n, m \le 2 \times 10^5, n \times m \le 10^6\)。
看到数最大值的位置相同的数列个数，自然可以想到建笛卡尔树后树形 dp。
记 \(f_{u, i}\) 表示当前在节点 \(u\)，填的数是 \(i\) 的方案数，\(g_{u, i} = \sum_{j \le i} f_{u, j}\)。
此时的限制是左儿子中的数都小于当前节点的数，右儿子中的数都小于等于当前节点的数。所以转移是：
\[f_{u, i} \leftarrow g_{ls_u, i - 1} \times g_{rs_u, i} \]然后直接转移就好了。
时间复杂度 \(O(nm)\)。
constexpr int MAXN = 2e5 + 9;
int n, m, a[MAXN], ls[MAXN], rs[MAXN];
vector<int> f[MAXN], stk;
void slv() {
n = Read<int>(), m = Read<int>();
for (int i = 1; i <= n; i ++) a[i] = Read<int>();
for (int i = 1; i <= n; i ++) {
while (stk.size() && a[stk.back()] < a[i])
ls[i] = stk.back(), stk.pop_back();
if (stk.size()) rs[stk.back()] = i;
stk.emplace_back(i);
}
int rt = stk.front();
function<void(int)> dp = [&](int u) {
if (!u) return; f[u].resize(m + 1);
dp(ls[u]), dp(rs[u]);
for (int i = 1; i <= m; i ++) {
f[u][i] = mul(f[ls[u]][i - 1], f[rs[u]][i]),
cadd(f[u][i], f[u][i - 1]);
}
return;
};
f[0].resize(m + 1);
for (int i = 0; i <= m; i ++) f[0][i] = 1;
dp(rt);
Write(f[rt][m], '\n');
return;
}