如果m比较小其实可以裸上莫队，如果不强制在线可以离线然后树状数组
考虑强制在线怎么做。记last[i]为前一个与a[i]相等的位置，若不存在则为0。对于询问(L,R)我们统计的实际上是last[i]<L的数量，这个用主席树做就十分显然了

BZOJ 1878
对于该题，离线的做法是树状数组或者线段树。

如果强制在线的话，可以用主席树做到O(mlogn)。

考虑到这样一个性质，对于询问[l,r]出现的数字种数。其答案就是to[i]>r的数字数。 其中to[i]表示的是第i个数的下一个相同的数出现的下标，没有则=n+1.

很幸运这个性质是满足区间减法的，也就是说对于[1,r]和[1,l-1]的to[i]域，是可以相减得到[l,r]的to[i]域的。

于是我们可以用主席树来解决这个问题。

对于一组询问，实际上就是求[l-1,r]这颗线段树上的区间[r+1,n+1]的出现次数总和。