P11911 [PA 2025] 集合 1 / Zbiory 1

PA 2025 trial round t1. 由于评测机性能差距，微调了 TL 和 ML。 **请注意本题非同寻常的时空限制。**

给定正整数 $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$，则 $A_{i}=A_x\cup A_y$； - 当 $op_i=2$ 时，给定参数 $x,y$，则 $A_{i}=A_x\cap A_y$； - 当 $op_i=3$ 时，给定参数 $x$，则 $A_{i}=U\backslash A_x$（即 $A_i=\{j:j\in U,j\not\in A_x\}$）。 接着有 $q$ 次询问，每次询问给定两个正整数 $x,y$，问是否有 $y\in A_x$。

第一行，三个正整数 $n,m,q$。 以下 $m$ 行，第 $i$ 行要么是 $1$ 或 $2$ 后面跟两个正整数，要么是 $3$ 后面跟一个正整数，表示第 $n+i$ 个集合的构造方式。 接下来 $q$ 行，每行两个正整数 $x,y$（$1 \le x \le n+m,\ 1 \le y \le n$），表示一次询问。

对于每组询问，输出一行，如果 $y\in A_x$，输出 $\tt{TAK}$，否则输出 $\tt{NIE}$。

- $1\le n\le 5\times 10^4$； - $1\le m\le 4\times 10^5$； - $1\le q\le 10^6$； - $1\le x_i,y_i