P17087 [COTS 2026] Addition / Zbrajanje (No data yet).

2s, 512M.

Consider integer lattice points in $k$-dimensional coordinates. We use an array $a=[a_1,\ldots,a_k]$ to restrict the coordinate range: define $S_a=\{(x_1,x_2,\ldots,x_k) \mid \forall 1\le i\le k,0\le x_i\lt a_i\}$. For two integer points $x=(x_1,\ldots,x_k),y=(y_1,\ldots,y_k)$ in $S_a$, define their **sum** as $x+y=((x_1+y_1)\bmod a_1,\ldots, (x_k+y_k)\bmod a_k)$. For arrays $a,b$, define $S_a,S_b$ to be **isomorphic** (Isomorphic) if and only if there exists an **addition-preserving** **bijection** $H:S_a\to S_b$. > > The mapping $H$ is **addition-preserving** if and only if: $\forall x,y\in S_a$, $H(x+y)=H(x)+H(y)$. > > Note: the addition on the left-hand side is defined in $S_a$, while the addition on the right-hand side is defined in $S_b$. > **Note that the lengths of $\boldsymbol{a,b}$ are not necessarily the same**. ::::info[A more plain description] For arrays $a,b$, define $S_a,S_b$ to be **isomorphic** (Isomorphic) if and only if there exists a mapping $H:S_a\to S_b$ such that: - $\forall x,y\in H(x),x\neq y\implies H(x)\neq H(y)$. In other words, different elements in $S_a$ are mapped to different elements in $S_b$. - $\{H(x) \mid x\in S_a\}=S_b$. In other words, every element in $S_b$ is mapped to exactly once. - $H$ is addition-preserving. In other words, let $x,y\in H(x)$, and let $z=x+y$. No matter how $x,y$ are chosen, we always have $H(z)=H(x)+H(y)$. :::: You are given an array $n=[n_1,\ldots,n_N]$ of length $N$. There are $Q$ operations of the following forms: - $\texttt{1}$ $i$ $x$: set $n_i\gets x$. - $\texttt{2}$ $l_1$ $r_1$ $l_2$ $r_2$. Let $a=[n_{l_1},\ldots,n_{r_1}]$ and $b=[n_{l_2},\ldots,n_{r_2}]$. Determine whether $S_a$ and $S_b$ are isomorphic. **Note that the lengths of $\boldsymbol{a,b}$ are not necessarily the same**.

The first line contains an integer $N$（$1 \le N \le 3 \cdot 10^5$）, denoting the length of the array. The second line contains $N$ integers $n_1, \dots n_N$（$1\le n_i\le 10^6$）. The third line contains an integer $Q$（$1 \le Q \le 3 \cdot 10^5$）, denoting the number of queries. In the next $Q$ lines, each line contains a query in one of the following formats: - $\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$）。 **Note that the lengths of the two intervals are not necessarily the same**.

For each query of type $\texttt{2}$, if they are isomorphic, output $\texttt{DA}$ on one line; otherwise output $\texttt{NE}$ on one line.

### Sample Explanation Below is the explanation for sample $2$. When $a=[2, 3]$ and $b=[6]$, $S_a$ and $S_b$ are isomorphic. One valid bijection $H$ is as follows: - $H((0, 0)) = (0)$； - $H((1, 1)) = (1)$； - $H((0, 2)) = (2)$； - $H((1, 0)) = (3)$； - $H((0, 1)) = (4)$； - $H((1, 2)) = (5)$； It can be shown that when $a=[2, 2]$ and $b=[4]$, $S_a$ and $S_b$ are not isomorphic. It is not hard to see that **the lengths of $\boldsymbol{a,b}$ are not necessarily the same**. ### Subtasks | Subtask | Score | Constraints | | :---: | :---: | :--- | | $1$ | $17$ | At any time, all $n_i$ are prime numbers. | | $2$ | $14$ | At any time, all $n_i$ are powers of $2$. | | $3$ | $33$ | $Q = 1$. | | $4$ | $36$ | No additional constraints. | Translated by ChatGPT 5