RT
看到一道经典的数据结构题，维护长度N的序列，要求支持查询一段区间内出现次数最多的数是什么，有多个的话输出最小的一个。要求在线算法。
这题乱搞做法实在很多，但今天我看到了一个O(n^1.5) -O(n^0.5)的做法，实在很NB，所以实现了一下。
先把各种做法列一下：
如果可以离线算法，那可以把查询[l,r]表示成点(l,r)然后从(l,r)转移到(l’,r’)估价函数可以用abs(l-l’)+abs(r-r’),于是用平面图曼哈顿最小生成树O(nlgn)求出一个比较优的转移顺序，然后可以证明转移总代价是O(n^1.5+Qn^0.5)级别的，时间复杂度O(n^1.5+Qn^0.5). 还有一种不用蛋疼生成树的方法，直接把横轴分成O(n^0.5)段，每段里直接按纵轴上升次序搞，显然横轴转移代价不超过n^1.5,纵轴转移代价不超过Qn^0.5，所以时间复杂度还是O(n^1.5+Qn^0.5),但是不用写蛋疼生成树了
但这题要在线…… 一个做法是分成L块，然后所有的连续的块段里头每个数出现了多少次全都记下来，时间复杂度O(L^2*n),然后查询时候就直接找到最大的能覆盖的那个块段，然后剩下的不被覆盖的元素显然是O(N/L)级别的，因为之前已经把每个数出现了多少次记下来了，现在直接暴力改即可，查询是O(n/L)的，折中取L=n^(1/3)，时间复杂度O(N^(5/3)) - O(n^(2/3))
还有一个做法也是分成L块，然后连续的块段里直接记录最优解，这样复杂度O(nL)的，然后考虑查询[l,r],同样找到能覆盖的最大的块段，那么最优解只有两种情况：1.那个块段的最优解. 2. 某个不被块段覆盖的数。显然不被块段覆盖的数是O(n/L)级别的，然后任务就转化成了：查询一个数在某个区间内出现次数。这个显然可以把每个数出现的位置用数据结构维护一下，然后转化成求rank. 因为没有修改，可以直接set,也可以vector完了二分查找。于是折中取L=n^0.5,时间复杂度为O(n^1.5) - O(n^0.5lgn)
能做到O(n^1.5) - O(n^0.5)的做法是前一种做法的改进。我们要想办法去掉那个log…… 想一下查询一个数在一段区间内出现了多少次的暴力方法，显然是f[i,j]表示j在区间[1,i]出现了多少次，然后f[i,j]=f[i-1,j]当j!=d[i], f[i,j]=f[i-1,j]+1当j==d[i]…… 但这样显然是O(n^2)的…… 考虑f[i]到f[i+1]的转移实际就是修改了一个数…… 于是问题进一步转化成了：维护一个数列，要求支持：修改一个数，查询第X次修改完成时某个数的值（第X次修改完成后就的序列就是f[X]）。这种要求能“撤销”做下去的操作的题目，一种方法是离线，当然就会多出一个log变回成了前一种方法了，另一种方法就是函数式数据结构。
考虑用函数式数据结构维护这个东西。显然修改后N-1个元素都是可以重用的，真正变化的只有1个元素。这时候发现如果以序号为关键字建函数式完全二叉树维护的话查询和修改照样O(lgn)不行，因为我们必须做到查询O(1)。于是想到一个更暴力的方法就是直接分块然后函数式块状链表（其实是块状数组）维护。假设分成L块，那么修改的时候L-1块都可以重用，包含修改元素的那一块必须重新建，于是时间复杂度O(n/L+L)，显然取L=n^0.5就做到了O(n^0.5)，查询时候可以直接找到第X次修改前的那个块链，于是就O(1)了。于是总时间复杂度O(n^1.5) - O(n^0.5)
实际写起来并不是很烦，函数式块链那一段非常简短，只有十几行。
代码 http://ideone.com/cpfvd