下面是来自pz萌神的做法……
clj的区间众数解题报告中最后的带修改区间众数方法……就作为前置知识
有插入操作的话,可以这么考虑,我们可以攒size2个插入操作,就重新预处理重新分块,攒的这些操作,可以暴力判断,比如说可以攒sqrt(M)个操作。这样总时间复杂度就是
M/size2(重建次数)*N*size(重建复杂度) + M * (N/size+size2)(查询复杂度,每次询问把攒的数字暴力扫一遍……)。
我们不妨假设 操作数m等于数列长度n
然后我们 让 size= n^(1/3),size2=n^(2/3) 这样就靠谱了
总时间复杂度O(N^(5/3))……
求更好做法