绝对众数相关 ​

定义：序列a[1~n]中出现次数大于floor(n/2)的数
性质：
	绝对众数是众数
	任何一个可重集的绝对众数唯一
	两个可重集合并成新可重集，新的绝对众数如果存在，那必然是原来两个可重集的绝对众数之一
	端点一定的区间的绝对众数最多O(log)个
常见问题：

判定某个数是否是绝对众数：
	将是该数的设为1，否则设为-1，判断和是否是正的
	
	此做法可以扩展至判定某个数的出现次数形如>n/k的形式
	例如：x>=floor((x+y)/3)，解得 2x-y>-3，那么可以分别赋2，-1的权值，将其和与-3比较
	
	此做法的优势是不用考虑区间长度
区间绝对众数：
	摩尔投票法：
		区间信息是：绝对众数及其对消后的次数
		该信息有可加性，可以结合线段树实现
		注意，其结果需要进行判定（不保证一定有绝对众数）
		
		该做法可以扩展至求出现次数大于n/k的数：
			具体的，维护k-1个可能的绝对众数a[1~k-1]，我们先考虑加入一个数x的情况
			若x在a序列中出现过，则将其次数++
			否则，看有没有空的位置，有就给x
			否则，就给所有的数的次数--
			同样也要判定合法性
	概率做法：
		每次在区间中随机一个数判定
		非常容易扩展到n/k的情况
	中位数做法：
		绝对众数一定是中位数
		可以用主席树实现
		
		扩展有限，只能扩展到n/2+dt的情况
例题：
P3765
[ARC159F] Good Division：是P4062的强化版
	首先有平方的1D/1D的DP，瓶颈在转移
	直接套分支结构DS不行，那只能上分治了
	利用log结论和信息合并的结论，可以得到分治区间内有用的绝对众数是log的

定义：序列a[1~n]中出现次数大于floor(n/2)的数
性质：
	绝对众数是众数
	任何一个可重集的绝对众数唯一
	两个可重集合并成新可重集，新的绝对众数如果存在，那必然是原来两个可重集的绝对众数之一
	端点一定的区间的绝对众数最多O(log)个
常见问题：

判定某个数是否是绝对众数：
	将是该数的设为1，否则设为-1，判断和是否是正的
	
	此做法可以扩展至判定某个数的出现次数形如>n/k的形式
	例如：x>=floor((x+y)/3)，解得 2x-y>-3，那么可以分别赋2，-1的权值，将其和与-3比较
	
	此做法的优势是不用考虑区间长度
区间绝对众数：
	摩尔投票法：
		区间信息是：绝对众数及其对消后的次数
		该信息有可加性，可以结合线段树实现
		注意，其结果需要进行判定（不保证一定有绝对众数）
		
		该做法可以扩展至求出现次数大于n/k的数：
			具体的，维护k-1个可能的绝对众数a[1~k-1]，我们先考虑加入一个数x的情况
			若x在a序列中出现过，则将其次数++
			否则，看有没有空的位置，有就给x
			否则，就给所有的数的次数--
			同样也要判定合法性
	概率做法：
		每次在区间中随机一个数判定
		非常容易扩展到n/k的情况
	中位数做法：
		绝对众数一定是中位数
		可以用主席树实现
		
		扩展有限，只能扩展到n/2+dt的情况
例题：
P3765
[ARC159F] Good Division：是P4062的强化版
	首先有平方的1D/1D的DP，瓶颈在转移
	直接套分支结构DS不行，那只能上分治了
	利用log结论和信息合并的结论，可以得到分治区间内有用的绝对众数是log的