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

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

对出现次数 $$$ \gt B$$$ 的颜色，同样需要建出虚树和求边权，将询问拍到离散化后的编号区间上，对每个离散化后的编号将其权重设为与之相关的点、边数量之和，按这个权重分块跑回滚莫队，颜色出现次数为 $$$x$$$ 时复杂度为 $$$O(x\sqrt m +m)$$$. 用可撤销并查集复杂度不是很对，需要一些神秘处理.

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

注：I 里那个做法不太行是因为套到这个题上那个标黑操作变成了翻转，这个没法维护.