题解

显然每种颜色贡献独立，考虑按出现次数根号分治，设分治阈值 $B$。

对出现次数 $< B$ 的颜色，建出其虚树，虚树的边权为对应路径上的边编号 $[\min,\max]$。显然有效的编号数只有 $O(B)$ 个，预处理 $O(B^2)$ 个区间答案后做一次二维差分，最后全部拉出来做一次二维数点，点数 $O(nB)$， 询问数为 $m$，使用 $O(1)-O(\sqrt n)$ 分块。

对出现次数 $> B$ 的颜色，同样需要建出虚树和求边权，将询问拍到离散化后的编号区间上，对每个离散化后的编号将其权重设为与之相关的点、边数量之和，按这个权重分块跑回滚莫队，颜色出现次数为 $x$ 时复杂度为 $O(x\sqrt m +m)$。用可撤销并查集复杂度不是很对（不过没卡），需要一些神秘处理。这里需要两层并查集，加入右端点用第一层并查集，回滚的时候先在第一层并查集上查，再用查到的点在第二层并查集上查一次，这样第二层并查集涉及到的点数只有 $O(x/\sqrt{m})$ 个，可以保证复杂度正确。

于是总复杂度是 $O(n\sqrt m+m\sqrt n)$。