题解：

题目定义了由三元基本集合组成的两个序列 $A$ 和 $B$，要求回答多次区间询问：$A[l..r]$ 能否通过一个全局排列 $p$ 映射为 $B[l..r]$。

关键难点：

• $n \leq 2\times 10^5$, $q \leq 10^6$，需要 $O(\log n)$ 或 $O(1)$ 的查询处理
• 不能对每个询问都检查所有排列（$m!$ 不可能）
• 需要找到快速判断两个集合序列“等价”的数学或组合条件

核心观察与转化

1. 排列不变性
如果存在排列 $p$ 使得 $f_p(A[i]) = B[i]$ 对所有 $i$ 成立，那么 $A$ 和 $B$ 的关系必须满足某种结构一致性。

2. 集合内的标号是任意的
因为 $p$ 可以任意置换元素，所以每个三元集合内的具体数字没有绝对意义，只有集合之间的对应关系有意义。

3. 映射为图的同构问题
我们可以把问题转化为图论问题：构造图 $G_A$ 和 $G_B$，其中顶点是 $1..m$，每个三元集合 $\{a,b,c\}$ 对应一个三角形（三条边）。
那么 $A[l..r]$ 和 $B[l..r]$ 等价，当且仅当这两个区间对应的子图同构。

但是图的同构判断很困难，且需要快速回答区间询问。

4. 使用 Hash 的解法（标准解法思路）
标准做法是给每个元素分配一个随机权值，然后对每个三元集合计算一个哈希值，确保在排列 $p$ 下哈希值不变（或按某种规则变换）。然后问题转化为判断两个哈希序列是否可以通过一个“偏移”匹配。

更具体地，对于每个位置 $i$：

• $A[i] = \{x,y,z\}$
• 定义 $h_A(i) = w_x \oplus w_y \oplus w_z$（或其它对称函数）
• 定义 $g_A(i) = w_x \cdot w_y \cdot w_z$（或其它对称函数）

由于 $p$ 是排列，它将权值 $w_u$ 映射为 $w_{p[u]}$。如果存在这样的 $p$，那么 $A$ 和 $B$ 在每个位置上的哈希值的多重集应该匹配。

5. 区间询问处理
对每个区间 $[l,r]$，我们需要检查是否存在一个排列 $p$，使得将 $A$ 的哈希序列映射为 $B$ 的哈希序列。这等价于检查两个多重集是否可以通过一个一一映射匹配。

实际标程使用的方法是：

• 给每个元素 $u$ 分配两个随机 64 位整数 $(R1[u], R2[u])$
• 对每个三元组 $\{x,y,z\}$，计算：

  hash1 = R1[x] ^ R1[y] ^ R1[z]
  hash2 = R2[x] ^ R2[y] ^ R2[z]
  

• 令 $H_A(i) = (hash1, hash2)$，$H_B(i)$ 同理
• 对于区间 $[l,r]$，收集 $A$ 的所有三元组对应的哈希对，和 $B$ 的所有哈希对
• 检查这两个集合能否通过一个固定的双射匹配（因为同一个 $p$ 作用于所有位置）

为了快速回答区间询问，通常需要莫队算法或前缀哈希 + 数据结构。

---

C 语言实现框架

由于完整实现非常长，我给出核心框架和关键函数：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>

typedef unsigned long long ull;
typedef long long ll;

#define MAX_N 200005
#define MAX_M 600005
#define MAX_Q 1000005

int n, m, q;
int A[MAX_N][3], B[MAX_N][3];

// 随机权值
ull RA1[MAX_M], RA2[MAX_M];
ull RB1[MAX_M], RB2[MAX_M];

// 哈希值
ull hashA1[MAX_N], hashA2[MAX_N];
ull hashB1[MAX_N], hashB2[MAX_N];

// 前缀和（用于快速区间哈希）
ull preA1[MAX_N], preA2[MAX_N];
ull preB1[MAX_N], preB2[MAX_N];

// 莫队相关
typedef struct {
    int l, r, id;
} Query;

Query queries[MAX_Q];
char ans[MAX_Q][4]; // "Yes" or "No"

// 生成随机 64 位整数
ull rand_ull() {
    ull x = rand();
    x = (x << 32) | rand();
    return x;
}

// 初始化随机权值
void init_random() {
    srand(time(NULL));
    for (int i = 1; i <= m; i++) {
        RA1[i] = rand_ull();
        RA2[i] = rand_ull();
        RB1[i] = rand_ull();
        RB2[i] = rand_ull();
    }
}

// 计算哈希
void compute_hash() {
    for (int i = 1; i <= n; i++) {
        // A[i] 的哈希
        int x = A[i][0], y = A[i][1], z = A[i][2];
        hashA1[i] = RA1[x] ^ RA1[y] ^ RA1[z];
        hashA2[i] = RA2[x] ^ RA2[y] ^ RA2[z];
        
        // B[i] 的哈希
        x = B[i][0]; y = B[i][1]; z = B[i][2];
        hashB1[i] = RB1[x] ^ RB1[y] ^ RB1[z];
        hashB2[i] = RB1[x] ^ RB1[y] ^ RB1[z];
        
        // 前缀和（用于快速区间异或和）
        preA1[i] = preA1[i-1] ^ hashA1[i];
        preA2[i] = preA2[i-1] ^ hashA2[i];
        preB1[i] = preB1[i-1] ^ hashB1[i];
        preB2[i] = preB2[i-1] ^ hashB2[i];
    }
}

// 快速判断区间是否等价（简化版，实际需要更复杂的匹配检查）
bool check_interval(int l, int r) {
    // 区间异或和
    ull xorA1 = preA1[r] ^ preA1[l-1];
    ull xorA2 = preA2[r] ^ preA2[l-1];
    ull xorB1 = preB1[r] ^ preB1[l-1];
    ull xorB2 = preB2[r] ^ preB2[l-1];
    
    // 简单检查：如果两个区间的哈希多重集完全匹配，那么异或和应该相等
    // 但注意：异或和相等是必要不充分条件，可能哈希冲突
    if (xorA1 != xorB1 || xorA2 != xorB2) {
        return false;
    }
    
    // 更严格的检查需要收集所有哈希值并进行匹配
    // 这里简化处理，实际需要莫队或数据结构
    return true;
}

// 比较函数用于莫队排序
int cmp_query(const void *a, const void *b) {
    Query *qa = (Query *)a;
    Query *qb = (Query *)b;
    int block_a = qa->l / 500; // 分块大小 sqrt(n)
    int block_b = qb->l / 500;
    if (block_a != block_b) return block_a - block_b;
    return (block_a & 1) ? (qb->r - qa->r) : (qa->r - qb->r);
}

// 莫队算法处理所有询问
void mo_algorithm() {
    // 对询问排序
    qsort(queries, q, sizeof(Query), cmp_query);
    
    // 初始化当前区间 [1,0] 空区间
    int curL = 1, curR = 0;
    
    // 用于统计哈希值出现次数的结构（简化表示）
    // 实际需要哈希表存储 (hash1, hash2) 对
    
    for (int i = 0; i < q; i++) {
        int L = queries[i].l;
        int R = queries[i].r;
        int id = queries[i].id;
        
        // 移动指针
        while (curL > L) {
            curL--;
            // 添加 hashA[curL] 到统计A
            // 添加 hashB[curL] 到统计B
        }
        while (curR < R) {
            curR++;
            // 添加 hashA[curR] 到统计A
            // 添加 hashB[curR] 到统计B
        }
        while (curL < L) {
            // 移除 hashA[curL] 从统计A
            // 移除 hashB[curL] 从统计B
            curL++;
        }
        while (curR > R) {
            // 移除 hashA[curR] 从统计A
            // 移除 hashB[curR] 从统计B
            curR--;
        }
        
        // 检查当前两个多重集是否匹配
        // 如果匹配则 ans[id] = "Yes"，否则 "No"
        // 这里简化处理
        strcpy(ans[id], check_interval(L, R) ? "Yes" : "No");
    }
}

int main() {
    // 从文件读取
    freopen("set.in", "r", stdin);
    freopen("set.out", "w", stdout);
    
    scanf("%d %d %d", &n, &m, &q);
    
    // 读取 A
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d", &A[i][0], &A[i][1], &A[i][2]);
    }
    
    // 读取 B
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d", &B[i][0], &B[i][1], &B[i][2]);
    }
    
    // 读取询问
    for (int i = 0; i < q; i++) {
        scanf("%d %d", &queries[i].l, &queries[i].r);
        queries[i].id = i;
    }
    
    // 初始化
    init_random();
    compute_hash();
    
    // 处理询问（这里用简化的 check_interval，实际需要莫队）
    for (int i = 0; i < q; i++) {
        printf("%s\n", check_interval(queries[i].l, queries[i].r) ? "Yes" : "No");
    }
    
    return 0;
}

---

算法核心解释

1. 哈希设计原理

我们给每个元素 $u$ 分配两个独立的随机权值 $(R1[u], R2[u])$。对于三元集合 $\{x,y,z\}$，计算：

• $h1 = R1[x] \oplus R1[y] \oplus R1[z]$
• $h2 = R2[x] \oplus R2[y] \oplus R2[z]$

这里使用异或的好处：

• 对称性：$\oplus$ 满足交换律，集合顺序不影响结果
• 可逆性：$a \oplus b \oplus b = a$
• 如果存在排列 $p$，则 $R1[p[x]]$ 是 $R1[x]$ 的一个排列

2. 区间等价条件

对于区间 $[l,r]$，收集：

• $S_A = \{(h1_A[i], h2_A[i]) \mid i \in [l,r]\}$
• $S_B = \{(h1_B[i], h2_B[i]) \mid i \in [l,r]\}$

我们需要检查是否存在一个一一映射 $\pi$（由排列 $p$ 诱导）使得 $\pi(S_A) = S_B$。

由于 $p$ 对所有位置一致，所以：

• $S_A$ 和 $S_B$ 作为多重集必须相同
• 且每个哈希值出现的次数必须匹配

3. 高效查询实现

对于 $q \leq 10^6$，需要 $O(1)$ 或 $O(\log n)$ 的查询。标准做法是：

方法一：前缀哈希 + 随机权值调整
更精妙的做法是：

1. 对每个元素 $u$ 分配随机权值 $w_u$
2. 定义 $val_A[i] = w_{x} + w_{y} + w_{z}$（对 $A[i] = \{x,y,z\}$）
3. 定义 $val_B[i]$ 类似
4. 但 $w_u$ 在排列 $p$ 下会映射为 $w_{p[u]}$
5. 通过精心设计，使得我们可以通过比较某些统计量来判断

方法二：莫队算法
如上面框架所示，使用莫队算法在线维护两个多重集，并实时检查是否匹配。

---

更完整的检查函数

下面是更完整的区间检查逻辑：

#include <uthash.h> // 需要 uthash 库

typedef struct {
    ull h1, h2;
    int countA, countB;
    UT_hash_handle hh;
} HashEntry;

HashEntry *hashTable = NULL;

// 添加哈希对到统计
void add_hash(ull h1, ull h2, int isA) {
    HashEntry *entry;
    HASH_FIND(hh, hashTable, &h1, sizeof(ull), entry);
    if (!entry) {
        entry = (HashEntry *)malloc(sizeof(HashEntry));
        entry->h1 = h1;
        entry->h2 = h2;
        entry->countA = 0;
        entry->countB = 0;
        HASH_ADD(hh, hashTable, h1, sizeof(ull), entry);
    }
    if (isA) entry->countA++;
    else entry->countB++;
}

// 移除哈希对
void remove_hash(ull h1, ull h2, int isA) {
    HashEntry *entry;
    HASH_FIND(hh, hashTable, &h1, sizeof(ull), entry);
    if (entry) {
        if (isA) entry->countA--;
        else entry->countB--;
        if (entry->countA == 0 && entry->countB == 0) {
            HASH_DEL(hashTable, entry);
            free(entry);
        }
    }
}

// 检查当前统计是否匹配
bool check_current() {
    HashEntry *entry, *tmp;
    HASH_ITER(hh, hashTable, entry, tmp) {
        if (entry->countA != entry->countB) {
            return false;
        }
    }
    return true;
}

---

复杂度分析

• 预处理：$O(n + m)$
• 莫队算法：$O((n+q)\sqrt{n})$，对于 $n=2\times 10^5, q=10^6$ 可能较慢
• 期望正确性：随机哈希，极低概率出错

优化方向

实际竞赛中，通常使用以下优化：

1. 分块预处理：将序列分块，预处理每块的哈希特征
2. 基数排序：对哈希值排序比较
3. 双哈希减少冲突：使用多组随机种子
4. 位运算优化：利用 64 位整数的快速运算

总结

这道题的核心是将集合序列等价问题转化为哈希值的多重集匹配问题，通过随机化哈希保证正确性（大概率正确），并使用高效数据结构（莫队或前缀和）处理区间查询。由于 $q$ 很大，需要精心设计以保证时间效率。