P9806 [POI 2022/2023 R1] poc

题目译自 [POI2022~2023R1 poc](https://sio2.mimuw.edu.pl/c/oi30-1/p/poc/)。

小 A 和小 B 在记录过往的车辆的类型！ 已知类型分别有 $1 \sim k$ 个，每种车辆必然属于其中之一。 小 A 按顺序细心地记录了所有的车辆的类型，但是贪玩的小 B 只按顺序记录了一部分车辆。 小 A 记录的内容长度为 $n$，小 B 记录的长度为 $m$。 称在小 A 记录中的第 $i$ 辆车“可能被 B 记录到”当且仅当在小 A 的记录中存在一个包含 $i$ 的子序列与小 B 所记录的完全相同。 保证小 B 记录的序列一定是小 A 记录的子序列，问哪些车辆是可能会被小 B 记录到，哪些没有。

第一行三个整数 $n,m,k \ (1 \leq n,m,k \leq 3 \times 10^5)$。 第二行一个长度为 $n$ 的序列，表示小 A 记录的序列。 第三行一个长度为 $m$ 的序列，表示小 B 记录的序列。 上述序列中的元素均满足 $1\leq$ 序列元素 $\leq k$。

对于每个小 A 记录到的车辆，请确定它能否被记录到，能输出 $1$，不能输出 $0$。

对于样例，存在如下的子序列： $(1,2,4,5)$，$(1,2,4,9)$，$(1,2,7,9)$，$(1,6,7,9)$，$(4,6,7,9)$。 注意到 $3$ 和 $8$ 一直都没被取到，故不能被小 B 记录到。 子任务分配如下： | 子任务编号 | 特殊性质 | 分值 | | :-----------: | :-----------: | :-----------: | | $1$ | $n,m \leq 100$ | $15$ | | $2$ | $n,m \leq 2000$ | $20$ | | $3$ | 每种类型的车辆最多被小 A 记录一次 | $15$ | | $4$ | 无附加限制 | $50$ | 时间限制：Subtask1 1s，Subtask2 10s，Subtask3 和 Subtask4 6s。