因为已经不能发题解了，所以发讨论区

类似 [Violet]蒲公英，分块，预处理 block_ans[b1][b2] 表示块 b1 ~ b2 的答案。

查询时，设 $l$ 在块 $b_l$，$r$ 在块 $b_r$，则答案为以下三部分的最大值：

1. ${block\_ans[b_l+1][b_r-1]}$
2. “块 $b_l$ 里的剩余部分”与其余部分得到的答案
3. “块 $b_r$ 里的剩余部分”与其余部分得到的答案

其中部分 2,3 用离散化颜色 + vector 存每种颜色对应的位置 + lower_bound 寻找位置实现，具体见代码

设块的大小为 $S$，则时间复杂度为 $\Theta(\frac{n^2}{S}+mS\log n)$

取 $S=\frac{n}{\sqrt{m\log n}}$ 可得最优复杂度 $\Theta(n\sqrt{m\log n})$

实际取 $S=n^{0.3}$ 左右比较快（考虑常数因素）

加个 O2 可以卡过

代码：https://gitee.com/hkxa/mycode/blob/master/luogu/P5906.cpp