[NOI2024] 集合

Luogu

IDLGP10785

Time1000ms

Memory512MB

DifficultyP6

2024NOIO2优化哈希 hashing双指针 two-pointer

小 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 也会散去。而我们和一个人保持连接的方式就是记住，仅此而已。 ## 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$，表示一次询问。 ## Output 输出 $q$ 行，每行包含一个字符串 $\tt{Yes}$ 或 $\tt{No}$，表示对应询问的两个序列是否等价。 [samples] ## Note **【样例 1 解释】** 以下用 $(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\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} | 测试点编号 | $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$ |

Samples

Input #1

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

Output #1

Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes

Input #2

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

Output #2

Input #3

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

Output #3

Input #4

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

Output #4

API Response (JSON)

{
  "problem": {
    "name": "[NOI2024] 集合",
    "description": {
      "content": "小 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",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10785"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 Y 和小 S 在玩一个游戏。\n\n给定正整数 $m$，定义**基本集合**为大小为 $3$，元素在 $1\\sim m$ 内的集合。例如：给定 $m=4$，则集合 $\\{1,2,3\\}$ 与集合 $\\{2,3,4\\}$ 都是基本集合。\n\n定义**集合序列**为由基本集合构成的序列，例如，$A=[\\{1,2,3\\},\\{2,3,4\\}]$ 是一个集合序列，其中 $A[1]=\\{1,2,3\\}$，$A...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments