[语言月赛202304] 写大作业

Luogu

IDLGB3748

Time2000ms

Memory512MB

DifficultyP2

2023O2优化字符串（入门）语言月赛

扶苏为了写计算理论大作业已经 $36$ 小时没有合眼了。为了能快点睡觉，扶苏找到了 $n$ 份文献，第 $i$ 份文献是一个字符串 $s_i$，她打算把这些文献组合起来。具体来说，一共有两种操作： - `1 x y`：把文献 $s_x$ 整体拼接到 $s_y$ 的后面，然后删除 $s_x$。 - `2 x y`：查询 $s_x$ 和 $s_y$ 是否**相似**。我们保证在 `1 x y` 操作出现后，字符串 $s_x$ **不会**出现在接下来的任何操作中。这就是说，操作 $1$ 至多有 $n-1$ 次。 **相似**的定义是：对两个字符串 $s_x$ 和 $s_y$，如果存在一种重新排列 $s_x$ 的方法，使得重排后的 $s_x$ 和 $s_y$ 相等，则称 $s_x$ 和 $s_y$ **相似**。例如，假设 $s_1 = \texttt{ab}, s_2 = \texttt{cd}, s_3 = \texttt{abcd}$，则执行 `1 1 2` 后，$s_1$ 被删除，$s_2 = \texttt{cdab}, s_3 = \texttt{abcd}$；继续执行 `2 2 3` 后，因为可以把 $s_2$ 重排为 $\texttt{abcd}$，所以 $s_2$ 和 $s_3$ 相似。注意，操作 $2$ 不会对字符串做出实际修改。 ## Input 第一行是两个整数，分别表示文献的数量 $n$ 和操作的数量 $q$。接下来 $n$ 行，每行一个字符串，第 $i$ 行的字符串表示 $s_i$。接下来 $q$ 行，每行三个整数 $op, x, y$，其含义见『题目描述』。 ## Output 对个操作 $2$，输出一行一个字符串。如果 $s_x$ 和 $s_y$ 相似，则输出 $\texttt{Yes}$，否则输出 $\texttt{No}$。 [samples] ## Note ### 数据规模与约定 - 对 $30\%$ 的数据，保证 $n = 2$，$q = 1$。 - 对 $60\%$ 的数据，保证 $n \leq 6$，$q \leq 6$，$|s_i| \leq 6$。 - 对 $100\%$ 的数据，保证 $2 \leq n \leq 10^5$，$1 \leq q \leq 10^6$，$1 \leq o \leq 2$，$1 \leq x, y \leq n$，且输入字符串的总长度不超过 $10^6$，输入字符串仅含小写英文字母，且不是空串。

Samples

Input #1

4 4
ab
cd
abcd
abcc
1 1 2
2 2 3
2 3 4
2 2 4

Output #1

Yes
No
No

API Response (JSON)

{
  "problem": {
    "name": "[语言月赛202304] 写大作业",
    "description": {
      "content": "扶苏为了写计算理论大作业已经 $36$ 小时没有合眼了。 为了能快点睡觉，扶苏找到了 $n$ 份文献，第 $i$ 份文献是一个字符串 $s_i$，她打算把这些文献组合起来。 具体来说，一共有两种操作： - `1 x y`：把文献 $s_x$ 整体拼接到 $s_y$ 的后面，然后删除 $s_x$。 - `2 x y`：查询 $s_x$ 和 $s_y$ 是否**相似**。 我们保证在 `1 x",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3748"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "扶苏为了写计算理论大作业已经 $36$ 小时没有合眼了。\n\n为了能快点睡觉，扶苏找到了 $n$ 份文献，第 $i$ 份文献是一个字符串 $s_i$，她打算把这些文献组合起来。\n\n具体来说，一共有两种操作：\n\n- `1 x y`：把文献 $s_x$ 整体拼接到 $s_y$ 的后面，然后删除 $s_x$。\n- `2 x y`：查询 $s_x$ 和 $s_y$ 是否**相似**。\n\n我们保证在 `1 x...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments