P6514 [QkOI#R1] Quark and Strings

你需要维护一个字符串序列 $\{S_n\}$，其中有 $n$ 个字符串，初始全为空。接下来有 $q$ 次操作，支持两种操作，下面设当前为第 $i$ 次操作，且本题中字符集为 $[1,q]\cap \N_+$： - `1 l r`，表示在所有编号在 $[l,r]$ 内的字符串末尾添加字符 $i$，这里 $i$ 是一个 $[1,q]$ 范围内的整数。 - `2 l r`，表示询问所有编号在 $[l,r]$ 内的字符串的最长公共子序列长度。当 $l=r$ 时，我们认为其最长公共子序列长度即为该字符串的长度。

第一行两个正整数 $n,q$。 接下来 $q$ 行每行三个正整数形如 `1 l r` 或 `2 l r`。

对于每次操作 $2$，输出一行非负整数作为你的答案。

### 样例解释 对于第一组样例： 第一次操作后，序列为 $\{[1],[1],[1],[],[]\}$。 第二次操作后，序列为 $\{[1,2],[1,2],[1,2],[2],[2]\}$。 第三次操作，容易发现询问的最长公共子序列为 $[2]$，长度为 $1$。 --- ### 数据范围 **本题采用捆绑测试。** - Subtask 1（10 pts）：$n,q\le 500$。 - Subtask 2（20 pts）：$n,q\le 1000$。 - Subtask 3（15 pts）：$n\le 1000$，操作 $1$ 不超过 $500$ 次，时限 $2000$ms。 - Subtask 4（15 pts）：$n\le 1000$，操作 $2$ 不超过 $500$ 次，时限 $2000$ms。 - Subtask 5（40 pts）：无特殊限制，时限 $3000$ms。 对于 $100\%$ 的数据，$1\le n,q\le 10^5$，除了特殊标明的 Subtask，其它 Subtask 时限均为 $1000$ms。