P10785 [NOI2024] Set

Xiao Y and Xiao S are playing a game. Given a positive integer $m$, define a **basic set** as a set of size $3$ whose elements are within $1\sim m$. For example, when $m=4$, the sets $\{1,2,3\}$ and $\{2,3,4\}$ are both basic sets. Define a **set sequence** as a sequence made up of basic sets. For example, $A=[\{1,2,3\},\{2,3,4\}]$ is a set sequence, where $A[1]=\{1,2,3\}$ and $A[2]=\{2,3,4\}$ are both basic sets. For a permutation $p[1],p[2],\dots,p[m]$ of $1\sim m$ and a set $S\subseteq \{1,2,\dots,m\}$, define $f_p(S)$ as the set obtained by replacing each element $x$ in $S$ with $p[x]$, i.e., $f_p(S)=\{p[x]|x\in S\}$. For two set sequences $A,B$ of length $k$, define $A$ and $B$ to be **equivalent** if and only if there exists a permutation $p$ of $1\sim m$ such that applying the permutation $p$ to $A$ yields $B$. That is, for all $1\leq i\leq k$, $f_p(A[i])=B[i]$. Given two set sequences $A,B$ of length $n$, there are $q$ queries. Each time, Xiao S asks Xiao Y: given $l,r$, determine whether the set sequence $[A[l],A[l+1],\dots,A[r]]$ and the set sequence $[B[l],B[l+1],\dots,B[r]]$ are equivalent. Time flies, and Xiao S and Xiao Y will also drift apart. And the way we stay connected with someone is to remember, nothing more.

The first line contains three positive integers $n,m,q$, representing the length of the set sequences, the value range of elements, and the number of queries. The second line contains $3n$ positive integers. The $(3i-2)$-th, $(3i-1)$-th, and $(3i)$-th integers ($1\leq i\leq n$) are the three elements of $A[i]$. It is guaranteed that these three elements are all in $[1,m]$ and are pairwise distinct. The third line contains $3n$ positive integers. The $(3i-2)$-th, $(3i-1)$-th, and $(3i)$-th integers ($1\leq i\leq n$) are the three elements of $B[i]$. It is guaranteed that these three elements are all in $[1,m]$ and are pairwise distinct. The next $q$ lines each contain two positive integers $l,r$, representing one query.

Output $q$ lines. Each line contains a string $\tt{Yes}$ or $\tt{No}$, indicating whether the two sequences in the corresponding query are equivalent.

**[Sample 1 Explanation]** Below, $(l,r)$ denotes the query with parameters $l,r$: - For query $(1,1)$, let the permutation be $p=[1,2,4,3]$. Then $f_p(A_1)=\{p[1],p[2],p[3]\}=\{1,2,4\}=B[1]$, so the two sequences for this query are equivalent. - For queries $(1,2),(1,3),(1,4)$, since $A[1]=A[2]$ but $B[1]\neq B[2]$, the two sequences for these queries are all not equivalent. - For queries $(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)$, let the permutation be $p=[2,3,4,1]$. Then $f_p(A_2)=\{p[1],p[2],p[3]\}=\{2,3,4\}=B_2$, $f_p(A_3)=\{p[1],p[2],p[4]\}=\{1,2,3\}=B_3$, $f_p(A_4)=\{p[1],p[2],p[3]\}=\{2,3,4\}=B_4$, so the two sequences for these queries are all equivalent. **[Constraints]** For all testdata, it is guaranteed that: $1\leq n\leq 2\times 10^5$, $3\leq m\leq 6\times 10^5$, $1\leq q\leq 10^6$, $1\leq l\leq r\leq n$. ::cute-table{tuack} | Test Point ID | $n\leq$ | $m\leq$ | $q\leq$ | | :----------: | :----------: | :----------: | :----------: | | $1\sim 3$ | $50$ | $4$ | $50$ | | $4\sim 6$ | $50$ | $5$ | $50$ | | $7$ | $200$ | $4$ | $200$ | | $8$ | $200$ | $5$ | $200$ | | $9$ | $200$ | $4$ | $2\times 10^5$ | | $10$ | $200$ | $5$ | $2\times 10^5$ | | $11$ | $2\times 10^5$ | $4$ | $2\times 10^5$ | | $12$ | $2\times 10^5$ | $5$ | $2\times 10^5$ | | $13,14$ | $2\,000$ | $6\,000$ | $10^3$ | | $15,16$ | $2\,000$ | $6\,000$ | $10^6$ | | $17,18$ | $2\times 10^4$ | $6\times 10^4$ | $10^2$ | | $19,20$ | $2\times 10^5$ | $6\times 10^5$ | $10^6$ | Translated by ChatGPT 5