【求助】数颜色问题

没有吧= =

线段树？

没有什么靠谱的搞法呢。。这样吧。。
令a=n^(0.25)
把这些分成a块，预处理第a块到第b块，第c块到到第d块的答案a^3*n
询问就是先根据预处理的值得到一个结果，然后加入剩下的数，n/a
复杂度n^1.75，凑合着过？