D - Quark and Strings
$\text{Description}$
你需要维护一个字符串序列 $\{S_n\}$，其中有 $n$ 个字符串，字符集为 $[1,q]\cap N_+$，初始全为空。接下来有 $q$ 次操作，支持两种操作（设当前为第 $i$ 次操作）：
1 l r，表示在所有编号在 $[l,r]$ 内的字符串末尾添加一个字符 $i$（数字）2 l r，表示询问所有编号在 $[l,r]$ 内的字符串的最长公共子序列长度。
$n,q\le 10^5$
$\text{Solution}$
注意操作 $1$ 只会添加之前未出现过的字符，可以得知，现在添加的字符只会在这一次操作中出现，所以一个 $[L,R]$ 的修改操作，实际上只会对 $l\ge L,r\le R$ 的 $[l,r]$ 询问操作贡献 $1$ 。
我们可以将问题转换为以下问题：
维护一个矩阵，其中第 $i$ 行第 $j$ 列的元素为 $a_{i,j}$，初始全为 $0$。支持两个操作：
1 l r，表示对所有满足 $i,j\in[l,r]$ 的 $a_{i,j}$ 执行$\mathbf{a_{i,j}\gets a_{i,j}+1}$。2 l r，表示询问 $a_{l,r}$ 的值。
利用二维差分，可以将操作 $1$ 变为单点加 $1$，操作 $2$ 变为询问矩形内所有数的和，从而可以使用树套树解决。