P6514 [QkOI#R1] Quark and Strings

You need to maintain a sequence of strings $\{S_n\}$, where there are $n$ strings, all initially empty. Then there are $q$ operations, and two types of operations are supported. Let the current operation be the $i$-th one. The character set in this problem is $[1,q]\cap \N_+$: - `1 l r` means appending the character $i$ to the end of every string whose index is in $[l,r]$. Here $i$ is an integer in the range $[1,q]$. - `2 l r` means querying the length of the longest common subsequence of all strings whose indices are in $[l,r]$. When $l=r$, we consider the longest common subsequence length to be the length of that string.

The first line contains two positive integers $n,q$. The next $q$ lines each contain three positive integers in the form `1 l r` or `2 l r`.

For each operation $2$, output one line with a non-negative integer as your answer.

### Sample Explanation For the first sample: After the first operation, the sequence is $\{[1],[1],[1],[],[]\}$. After the second operation, the sequence is $\{[1,2],[1,2],[1,2],[2],[2]\}$. For the third operation, it is easy to see that the longest common subsequence queried is $[2]$, with length $1$. --- ### Constraints **This problem uses bundled testdata.** - Subtask 1 (10 pts): $n,q\le 500$. - Subtask 2 (20 pts): $n,q\le 1000$. - Subtask 3 (15 pts): $n\le 1000$, operation $1$ occurs no more than $500$ times, time limit $2000$ms. - Subtask 4 (15 pts): $n\le 1000$, operation $2$ occurs no more than $500$ times, time limit $2000$ms. - Subtask 5 (40 pts): no special restrictions, time limit $3000$ms. For $100\%$ of the data, $1\le n,q\le 10^5$. Except for the specially marked Subtasks, the time limit for the other Subtasks is $1000$ms. Translated by ChatGPT 5