这里主要是讲一下如何预处理以及时间复杂度的计算
首先来看方法一
预处理时，最外层循环是\(i\)，第二层循环是\(j\)，表示第\(i\)个块到第\(j\)个块
先讲一下区间众数如何维护，记\(sum[i]\)表示\(i\)这个数出现的次数
假设此时已经维护好了\([i,j]\)这些块的众数（记为\(most\)），而且也维护好了\(sum\)数组，当\(j+1\)时，我们依次循环这个块里面的每个数，设当前循环到\(k\)这个数字，那么令\(sum[k]++\)，并且将\(sum[k]\)与\(sum[most]\)比较，如果前者更大，令\(most=k\)，最后的\(most\)就是要求的众数
时间复杂度为\(O(\frac{N}{T} \cdot \frac{(1+T) \cdot T}{2})=O(NT)\)，注意每一次\(j+1\)后就有\(O(\frac{N}{T})\)个数不用再扫描了
那么还要维护每个数出现的次数，就要在\(j+1\)的时候复制一下\(cnt\)数组，时间复杂度为\(O(N)\)，算上外面两层循环，时间复杂度是\(O(NT^2)\)
再来看方法二
由于不用维护每个数出现的次数了，预处理的时间复杂度就退化为了\(O(NT)\)
我们再想办法把log优化掉
我们不用二分，而是用\(s[i][j]\)表示前\(i\)个块中\(j\)出现的次数
预处理也是类似的，复杂度为\(O(NT)\)
然后每次查询暴力区间中\(x\)出现的个数时，就可以变成\(O(1)\)了
标签：frac,NT,复杂度,most,sum,蒲公英,预处理 From： https://www.cnblogs.com/dingxingdi/p/17936680.html