总结出来有关众数的几个问题的算法，理解或有偏差，以后慢慢琢磨补充~
一、求众数的方法:
1、哈希表(数组存储,map映射)
2、排序后查找
3、利用平衡树（实际上map就是一棵红黑树）
以treap为例,每个节点维护两个信息:
键值Key:保存元素值,
优先级Pro:保存元素在序列中出现的个数
BST维护Key,大根堆维护Pro
其实这种方法效率和普通bst是类似的。不过如果有求"出现次数第k多的数"，
求所有众数或者删除某个数之后的众数(使用treap delete方法将节点下旋)，这样的算法仍然是高效的。
具体分析Orz
http://blog.csdn.net/oiljt12138/article/details/50704236
二、区间众数问题(无修改):Orz sillycross
【Violet6 蒲公英】
长度为n的序列,元素大小1~n,求区间众数
多次询问, 要求在线
n,q<=10^4
区间众数的离线算法
1、线段树维护区间每个数出现次数（满足区间减法）
单次询问转移代价：将区间[L,R]看作平面上点(L,R),每次转移代价即为两点间曼哈顿距离
询问转移的最小总代价：包含平面上所有(L,R)点==>平面图曼哈顿最小生成树O(nlogn)
可以证明转移次数为O（n^1.5+n^0.5*q)
则算法复杂度为O（n^1.5*logn+n^0.5*q*logn)
2、改进：平面图曼哈顿最小生成树不容易写..
求平面图曼哈顿最小生成树 实质：用可以接受的代价把所有点连接起来
在暴力方法基础上采取特殊的处理顺序，是常用的有力手法：
把横轴平均分成O（n^0.5)段,每段里直接按纵轴上升次序处理
(见左图)
保证了纵向不重复,横向重复少！
横向转移代价O（n^0.5*q)
纵向转移代价O（n^1.5)
则算法复杂度O（(n+q)*n^0.5）
看来"分块解决"的思想效果显著啊
在线算法
合并所查询区间的答案复杂度高
对比离线算法，复杂度低是因为可由已知花费较小代价转移到所求
不妨预处理出一些区间的答案，将所查询区间尽量向已知答案的区间靠，代价取决于两个区间的相似性
预处理多少区间？预处理那些区间？
假设分成S块,则每块大小为N/S.
序列长度N,元素集大小N,询问个数Q与N同阶
给出一个定理:
令集合为多重集合,即一个数可以出现多次
一个集合a的众数表示为mode(a)
那么考虑集合a,b,有mode(a∪b)∈mode(a)∪b
形象点说:
如果区间 [L,R] 能覆盖区间 [L',R'] ， 那么区间 [L,R] 的众数
或者就是区间 [L',R'] 的众数，
或者是位于 [L',R'] 之外但位于 [L,R] 内的某个数。
在这里:
答案要么是覆盖块的答案，要么是没被覆盖的元素
思路一:
预处理:
预处理每块:a[i][x] 第i块中x出现次数 O(S*N)
预处理连续多块:b[i][j][x] 第i块~第j块中x出现次数
b[i][j][x]=b[i][j-1][x]+a[j][x] O(S^2*N)
并记录出现最多的数出现的次数!
处理询问:
整块O(1)查询,边界暴力O(N/S)
时间复杂度:
我们要让O(S^2*N)=O(N*N/S)
所以 S=O(N^(1/3))
则该算法O(N^(5/3))-O(N^(2/3))
思路二:
预处理:
c[i][j] 左端点是第i块起点,右端点是j的区间(即区间[st[i],j])的众数
不需要记录每个数分别出现的次数?!
O(N*S)
查询:
这次边界只有左边不到N/S个元素了
如何预处理和暴力查询??
新的问题:
给定一个序列 询问一个数在一段区间内出现的次数
- 把每个数出现的位置放在 vector 或 set 里,转化成求某个数是第几大
每次回答 O(lgN)
- F[i][x] 数字x在[1,i]内出现的次数
对于每个数字,f[i]由f[i-1]转移的过程 实质是修改一个数
进一步问题:
维护一个序列，要求支持:
1)修改一个数
2)查询第i次修改完成时某个数的值 （第 i 次修改完成后的序列就是 f[i] ）
函数式数据结构嘛!!
函数式二叉树？ O(log N)不行
函数式块状链表 !
假设分成 T 块.
修改的时候 T-1 块都可以重用,包含修改元素的那一块必须重新建.
于是时间复杂度 O(N/T+T)
取 T=N^0.5 做到 O(N^0.5)
每次修改 查询时可以直接找到第 X 次修改前的那个块状结构
每次找块O(1),查询众数要在块链中查询O(N/S)次
取 S=N^0.5 ，算法总时间复杂度: O(N^1.5) – O(N^0.5)
- 注意到当前子问题满足区间减法<"部分和"思想>
Query(L,R,x)=Query(1,R,x)-Query(1,L-1,x)
预处理所有Query(1,ed[i],x)的答案
对于具有特殊性的询问:询问的端点都是分块的端点 O(1)解决
算法复杂度:O(N^1.5) – O(N^0.5)
常数小,易实现,而且没有用到任何高级数据结构!!
三、问题扩展:带修改的区间众数 Orz CLJ
预处理:
值x在第i个块内部的id
一个块内:A[b][i][x] 第b块的前i个数中x出现的次数
连续块中:C[i][x] 前i块中x出现的次数
（次数满足区间减法，故可由前缀得出区间次数）
Mx[i][j] 第i块到第j块中最大出现次数
Cnt[i] 出现了i次的值的个数
修改操作:将pos位置的x值修改为y
C[i][x]--;C[i][y]++;(belong[pos]<=i<=n) 需要修改O(n^0.5)
维护O(S^2)对块之间的mx(最多改变1)
询问操作:同上,回答询问F(I,x)
考虑上述最终解法,可以每次O(1)回答[l,r]之间有几个x的询问
时间复杂度:
取S=n^(1/3),而非S=n^(1/2)==>与朴素无异
预处理:O(n^(5/3))
修改:O(S^2)=O(n^(2/3))
询问:O(n/S)=O(n^(2/3))
则总时间复杂度:O((n+q)*n^(2/3))
评论 (0)
