题意回顾

• $n$ 个样品瓶，编号 $1$ 到 $n$
• $1$ 到 $k$ 号瓶有不同物质，$k+1$ 到 $n$ 号瓶为空
• $m$ 条有向边表示导管，形成 DAG（有向无环图）
• 任何时候只能打开一个导管夹
• 物质会留下沉淀，不能混合不同物质
• 对每个区间 $[l,r]$（$k+1 \le l \le r \le n$），定义 $f(l,r)$ 为能安全转移到该区间内样品瓶的最大物质种类数
• 求对每个 $x = 0,1,\dots,k$，满足 $f(l,r) = x$ 的区间个数

数据范围：$n \le 10^5$，$m \le 10^6$，$k \le 50$

---

关键观察

1. 物质传输的限制

由于任何时候只能打开一个导管夹，且物质会留下沉淀，这意味着：

• 每种物质必须沿着一条独立的路径传输到目标瓶
• 不同物质的传输路径不能有公共节点（除了起点）
• 因为经过公共节点会留下沉淀，污染其他物质

2. 问题转化

对于区间 $[l,r]$，$f(l,r)$ 等于能选择的不相交路径的最大数量，使得：

• 每条路径从某个源点 $s \in [1,k]$ 出发
• 每条路径的终点都在 $[l,r]$ 中
• 所有路径点不交（除了起点）

3. 利用 $k$ 小的特性

由于 $k \le 50$，可以考虑对每个源点集合计算信息。

---

算法核心

1. 预处理每个物质的可达集合

对每个源点 $i \in [1,k]$，计算它能到达的所有节点集合 $R_i$。

由于是 DAG，可以用 BFS 或 DFS 在 $O(n+m)$ 时间内计算。

2. 定义关键数组

设 $g(S)$ 表示能容纳源点集合 $S$ 中所有物质的最小右端点：

• 即存在一种方式，将 $S$ 中所有物质传输到区间 $[l, r]$ 中
• 且 $r$ 最小

计算方法：对每个源点 $i \in S$，选择它可达节点中编号最小的作为目标，但要确保所有路径点不交。

实际上，$g(S)$ 可以这样计算：

• 对 $S$ 中所有源点，找到一组不相交的路径到达某些目标节点
• 取这些目标节点编号的最大值作为 $g(S)$

3. 计算 $f(l,r)$

对于区间 $[l,r]$，$f(l,r)$ 是最大的 $|S|$ 满足 $g(S) \le r$ 且所有路径的起点都在 $S$ 中。

更精确地说：$f(l,r) = \max \{ |S| : g(S) \le r \}$

---

高效计算 $g(S)$

贪心匹配

对集合 $S$，我们想找到一组不相交路径，使得最大目标编号最小。

算法：

1. 将 $S$ 中源点按某种顺序排序
2. 对每个源点，选择它可达的编号最小的节点作为目标
3. 如果该节点已被占用，选择下一个最小的，依此类推
4. $g(S)$ 等于所有选择目标中的最大编号

实现细节

由于 $k \le 50$，可以枚举所有 $2^k$ 个子集 $S$，对每个 $S$ 用贪心计算 $g(S)$。

---

统计区间个数

定义数组

设 $cnt[x]$ 表示 $f(l,r) = x$ 的区间个数。

计算方法

对于每个集合 $S$，设 $r_{\min} = g(S)$，则：

• 对所有 $r \ge r_{\min}$，区间 $[l,r]$ 至少能容纳 $|S|$ 种物质
• 更精确地说：对固定的 $r$，满足 $f(l,r) \ge |S|$ 的 $l$ 的范围可以确定

实际上，我们可以：

1. 对每个 $r$，计算最大的 $|S|$ 满足 $g(S) \le r$
2. 这就是 $f(l,r)$ 的值
3. 然后统计每个值出现的次数

最终

1. 预处理所有 $2^k$ 个子集 $S$ 的 $g(S)$
2. 对每个 $r$ 从 $k+1$ 到 $n$：
   • 找到最大的 $t$ 使得存在大小为 $t$ 的集合 $S$ 满足 $g(S) \le r$
   • 这就是 $f(l,r)$ 对所有 $l$ 的最大值
   • 但需要更精细的计算：对每个 $r$，计算 $F(r) = \max\{|S| : g(S) \le r\}$
3. 统计 $cnt$ 数组

---

复杂度分析

• 枚举所有子集：$O(2^k \cdot k \cdot n)$？需要优化
• 实际可以 $O(2^k \cdot k + n)$ 完成
• $2^k \cdot k \le 2^{50} \cdot 50$ 太大，但 $k \le 50$ 时 $2^{50}$ 不可行

---

优化算法

关键观察

由于 $k$ 很小，可以用 DP 计算： 设 $dp[mask]$ 表示容纳集合 $mask$ 所需的最小右端点。

转移： $dp[mask] = \min\limits_{i \in mask} \max(dp[mask \setminus \{i\}], \text{minAvailableTarget}(i, mask))$

其中 $\text{minAvailableTarget}(i, mask)$ 表示在已占用 $mask \setminus \{i\}$ 的目标后，源点 $i$ 能选择的最小编号目标。

预处理

对每个源点 $i$，预处理它可达的所有节点，排序。

算法步骤

1. 初始化 $dp[0] = k$（空集合不需要任何目标）
2. 从小到大枚举 $mask$，计算 $dp[mask]$
3. 对每个 $mask$，记录 $cnt[|mask|]$ 对应的 $dp[mask]$ 值
4. 最后统计区间个数

---

统计答案

对每个 $r$，设 $maxVal[r] = \max\{|mask| : dp[mask] \le r\}$

则对区间 $[l,r]$，$f(l,r) = maxVal[r]$（因为我们可以总是选择最优的 $mask$）

所以 $cnt[x]$ = 满足 $maxVal[r] = x$ 的 $r$ 的个数 × 对应的 $l$ 的个数。

实际上，对每个 $r$，所有 $l \le r$ 都有相同的 $f(l,r)$ 值，所以： $cnt[x] = \sum\limits_{r: maxVal[r]=x} (r - k)$

---

总结

本题的核心解法：

1. 利用 $k$ 小的特点，枚举所有源点子集
2. 用 DP 计算容纳每个子集所需的最小右端点
3. 根据 DP 结果统计满足 $f(l,r)=x$ 的区间个数
4. 时间复杂度 $O(2^k \cdot k + n + m)$，可处理大规模数据

通过状态压缩 DP 和组合计数，高效解决了这个复杂的物质传输计数问题。