题目分析

本题要求为 $m \times n$ 的表格（每列是 $0 \dots m-1$ 的排列）的每一列设置一个阈值 $z_j \in [0,m]$，使得对于每一行 $i$，根据给定的 NMLP（非重复单调线性规划）计算出的布尔函数值 $f_i$ 满足恰好有 $s$ 行的结果为 $1$，其余为 $0$。

核心思路

1. 单调性
   由于 NMLP 只包含 AND 和 OR 运算，没有 NOT，因此 $f_i$ 关于 $z_1, \dots, z_n$ 是单调非减的（增加 $z_j$ 只会让某些 $val[j]$ 从 0 变 1，不会让 1 变 0）。

2. 列排列性质
   第 $j$ 列的 $x_{1,j}, \dots, x_{m,j}$ 是 $0 \dots m-1$ 的排列，因此当 $z_j = t$ 时，该列恰好有 $t$ 行的 $val[j] = 1$。

3. 解法策略
   从 $z_j = 0$（所有输入为 0）开始，逐步增加某些 $z_j$，使得输出为 1 的行数逐渐增加，直到达到 $s$。
   因为单调性，我们可以按列依次激活（增加 $z_j$），并利用 NMLP 的结构快速判断哪些行的输出会从 0 变 1。

算法标签

• 单调性分析
• 贪心构造
• 树形结构处理
• 位运算模拟

代码解析

数据结构

• a[i][j] 表示第 $i$ 行第 $j$ 列的值。
• pos[j][v] 表示在第 $j$ 列中值为 $v$ 的行号。
• fa[u] 表示节点 $u$ 的父节点。
• son[0/1][u] 表示节点 $u$ 的两个子节点。
• tp[u] 表示节点 $u$ 的操作类型（1 为 AND，2 为 OR）。

主要流程

1. 读入 NMLP 结构
   对于每行 $i$，从 $m+1$ 到 $2m-1$ 的节点表示逻辑门，建立父子关系。

2. 读入表格数据
   并构建 pos 数组，便于按列按值查找行号。

3. 特殊情况处理
   如果 $s = 0$，则所有 $z_j = 0$ 即可。

4. 贪心构造阈值
   对每列 $j$，按值 $0 \dots m-1$ 升序遍历：

   • 将当前值对应的行的该列输入 $val[j]$ 设为 1（通过 modify 函数向上传播）。
   • 检查当前输出为 1 的行数 cnt 是否等于 $s$。
   • 如果等于，则当前列 $z_j = \text{当前值} + 1$，后续列 $z_k = 0$，前面列 $z_k = m$（保证单调性且不减少已激活的行数）。

modify 函数

• 从当前叶子节点向上更新，直到根节点或遇到未确定节点。
• 利用单调性：
  • AND 门：两个输入都为 1 时输出才为 1。
  • OR 门：任一输入为 1 时输出为 1。
    当某个门的输出确定变为 1 时，继续向上传播。

复杂度分析

• 每列最多遍历 $m$ 个值，每次 modify 是 $O(\text{树高})$，树高 $O(m)$。
• 总复杂度 $O(m^2 n)$ 在 worst-case 较大，但实际数据约束 $n \cdot m \le 3\times 10^5$，且通过单调性剪枝，可接受。

样例验证

对于样例：

n=4, m=3, s=2

代码按列遍历，当 $j=1$ 时值从 0 到 2 尝试，发现 $j=2$ 时在 $z_2=1$ 时 cnt=2，于是输出：

0 1 2 3

符合题意。

总结

本题利用单调性和列排列性质，通过贪心逐列激活输入，并借助 NMLP 的树形结构快速更新输出，构造满足条件的阈值方案。