P17087 [COTS 2026] 加法 / Zbrajanje（暂无数据）

2s, 512M

考虑 $k$ 维坐标中的整点。我们用数列 $a=[a_1,\ldots,a_k]$ 限制坐标范围：定义 $S_a=\{(x_1,x_2,\ldots,x_k) \mid \forall 1\le i\le k,0\le x_i\lt a_i\}$。 对于 $S_a$ 中的两个整点 $x=(x_1,\ldots,x_k),y=(y_1,\ldots,y_k)$，定义其**和** $x+y=((x_1+y_1)\bmod a_1,\ldots, (x_k+y_k)\bmod a_k)$。 对于数列 $a,b$，定义 $S_a,S_b$ **同构**（Isomorphic），当且仅当存在**保加法**的**双射** $H:S_a\to S_b$。 > > 定义映射 $H$ **保加法**，当且仅当：$\forall x,y\in S_a$，$H(x+y)=H(x)+H(y)$。 > > 注记：等号左边的加法是定义在 $S_a$ 中的，而右边的加法是定义在 $S_b$ 中的。 **注意，这里 $\boldsymbol{a,b}$ 的长度未必相同**。 ::::info[更通俗的叙述] 对于数列 $a,b$，定义 $S_a,S_b$ **同构**（Isomorphic），当且仅当存在映射 $H:S_a\to S_b$，满足： - $\forall x,y\in H(x),x\neq y\implies H(x)\neq H(y)$。换言之，$S_a$ 中不同的元素映射到 $S_b$ 中不同的元素。 - $\{H(x) \mid x\in S_a\}=S_b$。换言之，$S_b$ 中的每个元素都恰好被映射到一次。 - $H$ 保加法。换言之，设 $x,y\in H(x)$，令 $z=x+y$。不论 $x,y$ 如何取，都有 $H(z)=H(x)+H(y)$。 :::: 给定长度为 $N$ 的数列 $n=[n_1,\ldots,n_N]$。有 $Q$ 次操作，形如： - $\texttt{1}$ $i$ $x$：令 $n_i\gets x$。 - $\texttt{2}$ $l_1$ $r_1$ $l_2$ $r_2$。 令 $a=[n_{l_1},\ldots,n_{r_1}]$，$b=[n_{l_2},\ldots,n_{r_2}]$。判断 $S_a$ 和 $S_b$ 是否同构。 **注意，这里 $\boldsymbol{a,b}$ 的长度未必相同**。

第一行包含一个整数 $N$（$1 \le N \le 3 \cdot 10^5$），表示数列的长度。 第二行包含 $N$ 个整数 $n_1, \dots n_N$（$1\le n_i\le 10^6$）。 第三行包含一个整数 $Q$（$1 \le Q \le 3 \cdot 10^5$），表示询问的数量。 在接下来的 $Q$ 行中，每行包含一个以下格式之一的询问： - $\texttt{1}$ $i$ $x$（$1\le i\le N$，$1\le x\le 10^6$）。 - $\texttt{2}$ $l_1$ $r_1$ $l_2$ $r_2$（$1 \le l_1 \le r_1 \le N$，$1 \le l_2 \le r_2 \le N$）。 **注意，这两个区间的长度未必相同**。

对于每个类型 $\texttt{2}$ 的询问，若同构则输出一行 $\texttt{DA}$，否则输出一行 $\texttt{NE}$。

### 样例解释 以下为样例 $2$ 解释。 $a=[2, 3]$ 和 $b=[6]$ 时，$S_a$ 和 $S_b$ 同构。一个合法的双射 $H$ 如下所示： - $H((0, 0)) = (0)$； - $H((1, 1)) = (1)$； - $H((0, 2)) = (2)$； - $H((1, 0)) = (3)$； - $H((0, 1)) = (4)$； - $H((1, 2)) = (5)$； 可以证明 $a=[2, 2],b=[4]$ 时，$S_a$ 和 $S_b$ 不同构。 不难看出，**$\boldsymbol{a,b}$ 的长度未必相同**。 ### 子任务 | 子任务 | 分数 | 限制条件 | | :---: | :---: | :--- | | $1$ | $17$ | 在任意时刻，所有的 $n_i$ 都是素数。 | | $2$ | $14$ | 在任意时刻，所有的 $n_i$ 都是 $2$ 的幂。 | | $3$ | $33$ | $Q = 1$ | | $4$ | $36$ | 无额外限制条件。 |