[QkOI#R1] Quark and Strings 官方题解

LCuter · 2020-05-03 18:01:38 · 题解

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] 内的字符串的最长公共子序列长度。

\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 变为询问矩形内所有数的和，从而可以使用树套树解决。