11172: NOI2024 - D1T1 集合
[Creator : ]
Description
小 Y 和小 S 在玩一个游戏。
给定正整数 $m$，定义基本集合大小为 $3$，元素在 $1\sim m$ 内的集合。例如：给定 $m=4$，则集合 $\{1,2,3\}$ 与集合 $\{2,3,4\}$ 都是基本集合。
定义集合序列为由基本集合构成的序列，例如，$A=[\{1,2,3\},\{2,3,4\}]$ 是一个集合序列，其中 $A[1]=\{1,2,3\}$，$A[2]=\{2,3,4\}$ 都是基本集合。
对于一个 $1\sim m$ 的排列 $p[1],p[2],\dots,p[m]$ 与集合 $S\subseteq \{1,2,\dots,m\}$，定义 $f_p(S)$ 为将 $S$ 内每一个元素 $x$ 置换为 $p[x]$ 后所得到的集合，即 $f_p(S)=\{p[x]|x\in S\}$。
对于两个长度为 $k$ 的集合序列 $A,B$，定义 $A$ 和 $B$ **等价**当且仅当存在一个 $1\sim m$ 的排列 $p$，使得 $A$ 置换排列 $p$ 后得到 $B$，即对于所有 $1\leq i\leq k$，$f_p(A[i])=B[i]$。
给定两个长度为 $n$ 的集合序列 $A,B$，有 $q$ 次询问。每次小 S 会询问小 Y，在给定 $l,r$ 的情况下，判断集合序列 $[A[l],A[l+1],\dots,A[r]]$ 与集合序列 $[B[l],B[l+1],\dots,B[r]]$ 是否等价。
时光荏苒，小 S 和小 Y 也会散去。而我们和一个人保持连接的方式就是记住，仅此而已。
给定正整数 $m$，定义基本集合大小为 $3$，元素在 $1\sim m$ 内的集合。例如：给定 $m=4$，则集合 $\{1,2,3\}$ 与集合 $\{2,3,4\}$ 都是基本集合。
定义集合序列为由基本集合构成的序列，例如，$A=[\{1,2,3\},\{2,3,4\}]$ 是一个集合序列，其中 $A[1]=\{1,2,3\}$，$A[2]=\{2,3,4\}$ 都是基本集合。
对于一个 $1\sim m$ 的排列 $p[1],p[2],\dots,p[m]$ 与集合 $S\subseteq \{1,2,\dots,m\}$，定义 $f_p(S)$ 为将 $S$ 内每一个元素 $x$ 置换为 $p[x]$ 后所得到的集合，即 $f_p(S)=\{p[x]|x\in S\}$。
对于两个长度为 $k$ 的集合序列 $A,B$，定义 $A$ 和 $B$ **等价**当且仅当存在一个 $1\sim m$ 的排列 $p$，使得 $A$ 置换排列 $p$ 后得到 $B$，即对于所有 $1\leq i\leq k$，$f_p(A[i])=B[i]$。
给定两个长度为 $n$ 的集合序列 $A,B$，有 $q$ 次询问。每次小 S 会询问小 Y，在给定 $l,r$ 的情况下，判断集合序列 $[A[l],A[l+1],\dots,A[r]]$ 与集合序列 $[B[l],B[l+1],\dots,B[r]]$ 是否等价。
时光荏苒，小 S 和小 Y 也会散去。而我们和一个人保持连接的方式就是记住，仅此而已。
Input
输入的第一行包含三个正整数 $n,m,q$，分别表示集合序列的长度，元素范围和询问次数。
输入的第二行包含 $3n$ 个正整数，第 $3i-2,3i-1,3i$（$1\leq i\leq n$）个正整数分别表示 $A[i]$ 的三个元素。保证这三个元素均在 $[1,m]$ 范围内且互不相同。
输入的第三行包含 $3n$ 个正整数，第 $3i-2,3i-1,3i$（$1\leq i\leq n$）个正整数分别表示 $B[i]$ 的三个元素。保证这三个元素均在 $[1,m]$ 范围内且互不相同。
接下来 $q$ 行，每行包含两个正整数 $l,r$，表示一次询问。
输入的第二行包含 $3n$ 个正整数，第 $3i-2,3i-1,3i$（$1\leq i\leq n$）个正整数分别表示 $A[i]$ 的三个元素。保证这三个元素均在 $[1,m]$ 范围内且互不相同。
输入的第三行包含 $3n$ 个正整数，第 $3i-2,3i-1,3i$（$1\leq i\leq n$）个正整数分别表示 $B[i]$ 的三个元素。保证这三个元素均在 $[1,m]$ 范围内且互不相同。
接下来 $q$ 行，每行包含两个正整数 $l,r$，表示一次询问。
Output
输出 $q$ 行，每行包含一个字符串 $\tt{Yes}$ 或 $\tt{No}$，表示对应询问的两个序列是否等价。
Constraints
对于所有测试数据保证：$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$。
Sample 1 Input
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
Sample 1 Output
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
以下用 $(l,r)$ 表示对 $l,r$ 的询问：
- 对于询问 $(1,1)$，令排列 $p=[1,2,4,3]$，则 $f_p(A_1)=\{p[1],p[2],p[3]\}=\{1,2,4\}=B[1]$，因此该询问对应的两个序列等价。
- 对于询问 $(1,2),(1,3),(1,4)$，由于 $A[1]=A[2]$ 但 $B[1]\neq B[2]$，因此这些询问对应的两个序列都不等价。
- 对于询问 $(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)$，令排列 $p=[2,3,4,1]$，则 $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$，因此这些询问对应的两个序列都等价。
- 对于询问 $(1,1)$，令排列 $p=[1,2,4,3]$，则 $f_p(A_1)=\{p[1],p[2],p[3]\}=\{1,2,4\}=B[1]$，因此该询问对应的两个序列等价。
- 对于询问 $(1,2),(1,3),(1,4)$，由于 $A[1]=A[2]$ 但 $B[1]\neq B[2]$，因此这些询问对应的两个序列都不等价。
- 对于询问 $(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)$，令排列 $p=[2,3,4,1]$，则 $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$，因此这些询问对应的两个序列都等价。
Sample 2 Input
20 4 20
2 3 4 1 3 4 1 3 4 1 3 4 2 3 4 1 3 4 2 3 4 2 3 4 1 3 4 2 3 4 1 2 3 2 3 4 1 2 3 1 2 4 1 2 3 1 2 4 1 2 4 1 2 3 2 3 4 1 2 4
1 2 4 1 2 4 2 3 4 2 3 4 1 2 3 2 3 4 1 3 4 1 3 4 2 3 4 1 2 3 2 3 4 1 2 3 1 3 4 1 3 4 1 2 4 1 2 4 1 2 3 1 2 3 1 3 4 1 2 4
1 15
10 20
20 20
17 17
17 17
5 13
19 19
12 17
2 5
15 15
10 12
8 11
4 8
1 18
11 19
5 10
4 16
11 16
13 18
1 20
Sample 2 Output
No
No
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
Sample 3 Input
200 5 200
2 4 5 1 4 5 1 4 5 2 4 5 1 4 5 3 4 5 1 2 4 2 3 4 1 4 5 1 4 5 2 4 5 1 4 5 3 4 5 1 3 5 2 3 4 1 4 5 1 2 5 1 3 4 2 3 5 2 3 5 2 3 4 2 3 5 1 4 5 3 4 5 3 4 5 2 3 4 1 2 4 1 4 5 1 4 5 1 4 5 1 4 5 1 3 5 2 4 5 1 2 4 1 3 5 3 4 5 1 4 5 1 4 5 1 2 4 2 3 4 2 4 5 1 2 4 1 2 5 1 2 4 3 4 5 1 2 4 1 4 5 1 4 5 1 2 4 1 4 5 3 4 5 1 2 4 3 4 5 1 4 5 1 2 5 1 4 5 1 4 5 1 3 4 2 3 4 2 3 5 1 4 5 2 3 4 1 3 4 1 4 5 1 2 4 1 2 5 1 4 5 1 4 5 1 4 5 1 4 5 1 3 5 1 2 4 1 4 5 1 2 4 1 2 4 1 2 5 1 4 5 1 3 4 1 3 5 2 4 5 1 2 4 1 4 5 1 2 4 1 3 4 1 3 4 1 3 5 3 4 5 1 2 5 1 4 5 1 4 5 1 3 5 1 4 5 1 4 5 1 4 5 1 2 4 2 3 4 2 3 5 2 3 4 2 3 5 2 4 5 1 2 3 1 4 5 1 2 5 1 4 5 1 3 4 1 4 5 1 2 4 1 4 5 1 2 5 1 2 4 3 4 5 1 4 5 1 4 5 1 4 5 1 2 4 2 4 5 2 4 5 1 2 4 1 4 5 1 4 5 1 4 5 1 4 5 1 2 4 1 4 5 2 4 5 1 4 5 1 4 5 1 2 5 1 2 5 1 4 5 2 4 5 1 4 5 2 3 4 1 2 3 3 4 5 1 3 4 1 3 5 1 4 5 1 4 5 1 4 5 1 2 4 3 4 5 1 2 4 1 4 5 1 4 5 1 4 5 1 2 5 2 3 4 1 3 5 1 4 5 1 2 3 1 3 5 1 4 5 1 4 5 2 4 5 2 4 5 3 4 5 1 2 4 1 4 5 1 2 5 3 4 5 1 3 4 1 2 4 1 3 5 3 4 5 1 2 4 1 4 5 1 2 4 1 4 5 2 4 5 2 3 4 3 4 5 1 4 5 1 4 5 1 2 4 2 4 5 1 2 4 1 2 4 1 3 4 3 4 5 1 3 4 2 3 5 2 4 5 1 3 4 1 4 5 1 2 5 1 3 5 1 4 5 2 4 5 1 2 4 1 4 5 2 4 5 1 4 5 2 4 5 1 2 5 1 3 4 1 3 5 1 4 5 1 2 4 1 2 5
1 4 5 2 3 4 2 3 5 2 4 5 1 4 5 1 3 4 3 4 5 2 4 5 1 3 4 1 3 5 3 4 5 1 4 5 1 2 4 2 4 5 1 4 5 1 3 5 1 3 4 1 4 5 1 2 4 1 4 5 1 3 4 3 4 5 1 2 5 1 4 5 1 4 5 1 3 4 1 2 3 1 2 5 1 2 5 1 2 5 1 2 5 2 4 5 1 3 5 1 2 3 2 4 5 1 4 5 1 2 5 1 2 5 1 2 3 1 3 4 1 3 5 1 2 3 2 3 5 1 2 3 1 4 5 1 2 3 1 2 5 1 2 5 1 2 3 1 2 5 1 4 5 1 2 3 1 4 5 1 2 5 2 3 5 1 2 5 1 2 5 1 2 4 1 3 4 3 4 5 1 2 5 1 3 4 1 2 4 1 2 5 1 2 3 2 3 5 1 2 5 1 2 5 1 2 5 1 2 5 2 4 5 1 2 3 1 2 5 1 2 3 1 2 3 2 3 5 1 2 5 1 2 4 2 4 5 1 3 5 1 2 3 1 2 5 1 2 3 1 2 4 1 2 4 2 4 5 1 4 5 2 3 5 1 2 5 1 2 5 2 4 5 1 2 5 1 2 5 1 2 5 1 2 3 1 3 4 3 4 5 1 3 4 1 4 5 1 2 4 1 3 4 1 4 5 2 4 5 1 4 5 1 4 5 1 3 4 1 2 5 1 2 4 2 4 5 1 3 4 1 4 5 1 2 4 1 2 3 1 2 4 1 3 4 1 4 5 1 3 4 2 3 5 1 4 5 2 4 5 2 3 5 3 4 5 1 2 5 1 2 4 1 2 3 1 3 4 1 3 4 2 4 5 1 2 5 1 2 4 1 4 5 1 2 5 2 3 4 1 4 5 1 4 5 1 4 5 1 2 4 1 4 5 1 4 5 1 2 5 1 4 5 3 4 5 1 4 5 2 4 5 1 4 5 1 4 5 1 2 3 1 2 4 1 4 5 1 2 4 2 4 5 1 4 5 1 2 5 2 3 4 1 2 4 1 4 5 1 4 5 1 4 5 1 4 5 1 4 5 1 2 4 1 4 5 1 4 5 1 4 5 1 4 5 1 2 4 1 4 5 1 2 4 1 4 5 1 4 5 1 4 5 1 4 5 1 3 5 2 4 5 1 4 5 1 4 5 1 2 4 3 4 5 1 2 5 1 4 5 1 4 5 1 3 5 1 4 5 2 3 4 1 3 5 1 4 5 1 2 3 1 4 5 1 4 5 1 3 4 2 3 5 2 4 5 1 4 5 2 4 5 1 2 3 2 3 5 1 3 4 1 3 4 1 3 5 1 4 5
97 158
78 191
174 186
50 136
119 163
123 172
121 131
177 181
163 173
181 185
186 199
136 161
188 197
91 108
8 146
36 79
140 150
81 149
116 184
100 168
48 179
170 178
100 140
199 199
47 151
149 193
167 200
162 187
39 133
145 156
94 119
94 198
179 184
58 62
67 144
64 139
61 163
51 126
131 157
22 45
134 174
47 152
187 188
107 122
176 188
10 10
119 167
44 159
34 163
103 178
93 158
22 85
84 96
33 116
95 184
181 198
61 125
19 65
122 143
149 173
55 181
148 176
96 99
94 114
57 200
167 183
72 97
93 137
81 199
190 197
12 177
97 155
71 188
87 180
145 190
64 189
132 195
113 164
90 136
135 199
22 56
114 137
19 131
59 178
140 193
62 179
176 185
194 200
121 192
198 198
164 196
34 182
51 56
73 171
135 174
41 94
176 183
12 52
136 196
4 91
110 123
164 195
20 99
30 113
57 136
180 195
18 34
19 181
56 118
106 129
28 76
131 193
74 80
190 195
116 183
108 117
109 117
178 185
60 116
85 131
1 168
110 154
71 73
40 175
194 197
105 150
185 188
104 198
27 128
30 145
91 129
185 191
49 72
185 191
12 109
154 194
59 92
169 180
191 191
131 145
146 165
69 95
106 142
62 178
178 178
119 169
34 176
160 180
118 153
5 177
186 200
54 152
101 115
193 200
184 185
60 112
103 103
74 183
195 199
2 160
148 194
12 75
163 199
43 138
5 80
47 136
17 115
166 186
96 106
58 146
92 190
87 176
73 80
181 194
78 143
80 150
7 26
129 144
194 196
193 196
194 199
135 146
194 199
94 190
87 182
8 177
30 172
101 190
17 105
67 174
120 177
72 140
77 126
182 195
92 92
68 149
19 60
159 172
198 199
132 199
Sample 3 Output
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
No
No
No
No
No
Yes
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
Yes
No
No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
No
Yes
No
No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
No