P11912 [PA 2025] 集合 2 / Zbiory 2

PA 2025 trial round t2. **请注意本题非同寻常的时空限制。**

> **问题。** > > 给定正整数 $n$ 和非负整数 $m$。定义全集 $U=\{1,2,\ldots,n\}$。 > > 构造 $(n+m)$ 个集合 $A_1,A_2,\ldots,A_{n+m}$： > > 1. 对于 $1\le i\le n$，$A_i$ 里的元素为 $U$ 中 $i$ 的倍数。 > 2. 对于 $n+1\le i\le n+m$，给定参数 $op_i$： > > - 当 $op_i=1$ 时，给定参数 $x,y$（$x,y\lt n+i$），则 $A_{i} =A_x\cup A_y$； > - 当 $op_i=2$ 时，给定参数 $x,y$（$x,y\lt n+i$），则 $A_{i}=A_x\cap A_y$； > - 当 $op_i=3$ 时，给定参数 $x$（$x\lt n+i$），则 $A_{i}=U\backslash A_x$（即 $A_i=\{j:j\in U,j\not\in A_x\}$）。 > > 定义问题的答案为 $A_{n+m}$。 给定正整数 $n$ 和目标集合 $B\subseteq \{1,2,\ldots,n\}$。构造非负整数 $m$ 和一组对应的参数，使得上述问题的答案为 $B$。 你需要保证 $0\le m\le 10^5$。可以证明本题一定有解。

第一行，两个正整数 $n,k$，其中 $|B|=k$。 第二行，$k$ 个正整数 $B_1,B_2,\ldots,B_k$，描述 $B$ 中的元素。

输出 $(m+1)$ 行： 第一行，一个非负整数 $m$。 接下来 $m$ 行，第 $i$ 行两个或三个正整数（格式见上），描述集合 $A_{n+i}$ 的生成方式。 你需要保证 $0\le m\le 10^5$，且格式符合【题目描述】中的限制。

- $1\le n\le 5\times 10^4$; - $B\subseteq \{1,2,\ldots,n\}$。