题目描述
小 Y 和小 S 在玩一个游戏。
给定正整数 m,定义 基本集合 为大小为 3,元素在 1∼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∼m 的排列 p[1],p[2],⋯,p[m] 与集合 S⊆{1,2,…,m},定义 fp(S) 为将 S 内每一个元素 x 置换为 p[x] 后所得到的集合,即 fp(S)={p[x]∣x∈S}。
对于两个长度为 k 的集合序列 A,B,定义 A 和 B 等价 当且仅当存在一个 1∼m 的排列 p,使得 A 置换排列 p 后得到 B,即对于所有 1≤i≤k,fp(A[i])=B[i]。
给定两个长度为 n 的集合序列 A,B,有 q 次询问:每次小 S 会询问小 Y,在给定 l,r 的情况下,判断集合序列 [A[l],A[l+1],⋯,A[r]] 与集合序列 [B[l],B[l+1],⋯,B[r]] 是否等价?
时光荏苒,小 S 和小 Y 也会散去。而我们和一个人保持连接的方式就是记住,仅此而已。
输入格式
从文件 set.in
中读入数据。
输入的第一行包含三个正整数 n,m,q,分别表示集合序列的长度、元素范围和询问次数。
输入的第二行包含 3n 个正整数,第 3i−2,3i−1,3i(1≤i≤n)个正整数分别表示 A[i] 的三个元素。保证这三个元素均在 [1,m] 范围内且互不相同。
输入的第三行包含 3n 个正整数,第 3i−2,3i−1,3i(1≤i≤n)个正整数分别表示 B[i] 的三个元素。保证这三个元素均在 [1,m] 范围内且互不相同。
接下来 q 行,每行包含两个正整数 l,r,表示一次询问。
输出格式
输出到文件 set.out
中。
输出 q 行,每行包含一个字符串 Yes
或 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
样例 1 解释
以下用 (l,r) 表示对 l,r 的询问:
- 对于询问 (1,1),令排列 p=[1,2,4,3],则 fp(A1)={p[1],p[2],p[3]}={1,2,4}=B[1],因此该询问对应的两个序列等价。
- 对于询问 (1,2),(1,3),(1,4),由于 A[1]=A[2] 但 B[1]=B[2],因此这些询问对应的两个序列都不等价。
- 对于询问 (2,2),(2,3),(2,4),(3,3),(3,4),(4,4),令排列 p=[2,3,4,1],则 fp(A2)={p[1],p[2],p[3]}={2,3,4}=B2,fp(A3)={p[1],p[2],p[4]}={1,2,3}=B3,fp(A4)={p[1],p[2],p[3]}={2,3,4}=B4,因此这些询问对应的两个序列都等价。
样例 2
见选手目录下的 set/set2.in
与 set/set2.ans
。
这个样例满足测试点 1∼3 的约束条件。
样例 3
见选手目录下的 set/set3.in
与 set/set3.ans
。
这个样例满足测试点 8 的约束条件。
样例 4
见选手目录下的 set/set4.in
与 set/set4.ans
。
这个样例满足测试点 15,16 的约束条件。
数据范围
对于所有测试数据保证:1≤n≤2×105,3≤m≤6×105,1≤q≤106,1≤l≤r≤n。
测试点编号 |
n≤ |
m≤ |
q≤ |
1∼3 |
50 |
4 |
50 |
4∼6 |
5 |
7 |
200 |
4 |
200 |
8 |
5 |
9 |
4 |
2×105 |
10 |
5 |
11 |
2×105 |
4 |
12 |
5 |
13,14 |
2,000 |
6,000 |
103 |
15,16 |
106 |
17,18 |
2×104 |
6×104 |
102 |
19,20 |
2×105 |
6×105 |
106 |