#P10785. [NOI2024] 集合

[NOI2024] 集合

题目描述

小 Y 和小 S 在玩一个游戏。

给定正整数 mm,定义基本集合为大小为 33,元素在 1m1\sim m 内的集合。例如:给定 m=4m=4,则集合 {1,2,3}\{1,2,3\} 与集合 {2,3,4}\{2,3,4\} 都是基本集合。

定义集合序列为由基本集合构成的序列,例如,A=[{1,2,3},{2,3,4}]A=[\{1,2,3\},\{2,3,4\}] 是一个集合序列,其中 A[1]={1,2,3}A[1]=\{1,2,3\}A[2]={2,3,4}A[2]=\{2,3,4\} 都是基本集合。

对于一个 1m1\sim m 的排列 p[1],p[2],,p[m]p[1],p[2],\dots,p[m] 与集合 S{1,2,,m}S\subseteq \{1,2,\dots,m\},定义 fp(S)f_p(S) 为将 SS 内每一个元素 xx 置换为 p[x]p[x] 后所得到的集合,即 fp(S)={p[x]xS}f_p(S)=\{p[x]|x\in S\}

对于两个长度为 kk 的集合序列 A,BA,B,定义 AABB 等价当且仅当存在一个 1m1\sim m 的排列 pp,使得 AA 置换排列 pp 后得到 BB,即对于所有 1ik1\leq i\leq kfp(A[i])=B[i]f_p(A[i])=B[i]

给定两个长度为 nn 的集合序列 A,BA,B,有 qq 次询问。每次小 S 会询问小 Y,在给定 l,rl,r 的情况下,判断集合序列 [A[l],A[l+1],,A[r]][A[l],A[l+1],\dots,A[r]] 与集合序列 [B[l],B[l+1],,B[r]][B[l],B[l+1],\dots,B[r]] 是否等价。

时光荏苒,小 S 和小 Y 也会散去。而我们和一个人保持连接的方式就是记住,仅此而已。

输入格式

输入的第一行包含三个正整数 n,m,qn,m,q,分别表示集合序列的长度,元素范围和询问次数。

输入的第二行包含 3n3n 个正整数,第 3i2,3i1,3i3i-2,3i-1,3i1in1\leq i\leq n)个正整数分别表示 A[i]A[i] 的三个元素。保证这三个元素均在 [1,m][1,m] 范围内且互不相同。

输入的第三行包含 3n3n 个正整数,第 3i2,3i1,3i3i-2,3i-1,3i1in1\leq i\leq n)个正整数分别表示 B[i]B[i] 的三个元素。保证这三个元素均在 [1,m][1,m] 范围内且互不相同。

接下来 qq 行,每行包含两个正整数 l,rl,r,表示一次询问。

输出格式

输出 qq 行,每行包含一个字符串 Yes\tt{Yes}No\tt{No},表示对应询问的两个序列是否等价。

4 4 10
1 2 3 1 2 3 1 2 4 1 2 3
1 2 4 2 3 4 1 2 3 2 3 4
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
见 set2.in/ans
这个样例满足测试点 1-3 的约束条件。

见 set3.in/ans
这个样例满足测试点 8 的约束条件。

见 set4.in/ans
这个样例满足测试点 15、16 的约束条件。

提示

【样例 1 解释】

以下用 (l,r)(l,r) 表示对 l,rl,r 的询问:

  • 对于询问 (1,1)(1,1),令排列 p=[1,2,4,3]p=[1,2,4,3],则 fp(A1)={p[1],p[2],p[3]}={1,2,4}=B[1]f_p(A_1)=\{p[1],p[2],p[3]\}=\{1,2,4\}=B[1],因此该询问对应的两个序列等价。
  • 对于询问 (1,2),(1,3),(1,4)(1,2),(1,3),(1,4),由于 A[1]=A[2]A[1]=A[2]B[1]B[2]B[1]\neq B[2],因此这些询问对应的两个序列都不等价。
  • 对于询问 (2,2),(2,3),(2,4),(3,3),(3,4),(4,4)(2,2),(2,3),(2,4),(3,3),(3,4),(4,4),令排列 p=[2,3,4,1]p=[2,3,4,1],则 fp(A2)={p[1],p[2],p[3]}={2,3,4}=B2f_p(A_2)=\{p[1],p[2],p[3]\}=\{2,3,4\}=B_2fp(A3)={p[1],p[2],p[4]}={1,2,3}=B3f_p(A_3)=\{p[1],p[2],p[4]\}=\{1,2,3\}=B_3fp(A4)={p[1],p[2],p[3]}={2,3,4}=B4f_p(A_4)=\{p[1],p[2],p[3]\}=\{2,3,4\}=B_4,因此这些询问对应的两个序列都等价。

【数据范围】

对于所有测试数据保证:1n2×1051\leq n\leq 2\times 10^53m6×1053\leq m\leq 6\times 10^51q1061\leq q\leq 10^61lrn1\leq l\leq r\leq n

测试点编号 nn\leq mm\leq qq\leq
131\sim 3 5050 44 5050
464\sim 6 55
77 200200 44 200200
88 55
99 44 2×1052\times 10^5
1010 55
1111 2×1052\times 10^5 44
1212 55
13,1413,14 20002\,000 60006\,000 10310^3
15,1615,16 10610^6
17,1817,18 2×1042\times 10^4 6×1046\times 10^4 10210^2
19,2019,20 2×1052\times 10^5 6×1056\times 10^5 10610^6