题目
有个数列，你要维护它，支持区间赋值、区间加一、区间询问出现次数大于等于(p*(r-l+1))的数有哪些。（题目的那个除以(100)就省掉了哈）
思考历程
总感觉这题不好直接用数据结构来搞。
然后就想到了分块，每个块维护各自的答案。
考虑合并两个区间的答案：
假如某个数在两个区间的答案中都没有出现过，那么它在两个区间的并的答案中也不会出现；
假如都出现过，那么它在两个区间的并的答案中一定会出现；
否则它是否在两个区间的并的答案需要额外计算。我们需要知道它在两个区间中的出现次数。
考虑整块（散块随便做），以下都是忽略了散块的结果：
我们知道了每个块的答案，那么它们的并的答案一定被这些块的答案的并所包含。
我们只需要在它们中寻找答案。
一开始，我有个这样的思路：从左到右一个一个将区间合并起来，如果是一个长的区间和一个短的区间合并，那么短的区间的答案对总体答案的影响会小一些。我们能否多维护一些东西，就是可能成为答案的那些值呢（可以发现这是有限制的）？推一波式子，我发现，随着长区间和短区间长度的比值越来越大，那些可能成为答案的值的个数，将会越来越少（图象是个双曲线）。以(p=0.2)举例，当比值大于(24)时，就不用维护可能成为答案的值的个数了。不过(24)可能有点大，那就在比值等于(8)时，求出前(10)个众数，接下来随着比值越来越大，有必要维护的数的个数越来越少。所以只需要暴力前(8)块，后面的就可以快速合并了。
然而这个东西看起来好像不是很靠谱。
接着我又发现了一条有趣的性质：
设长度为(l)，满足答案的数必须要出现(pl)次。设块大小为(K)，假如将这(pl)个数塞到尽量少的块中，就需要在至少(lfloorfrac{pl}{K}
floor)个块的答案中出现。利用这个性质对答案进行筛选。
所有的块加起来一共记了(frac{l}{pK})个答案，两式一除，得到大概(frac{1}{p^2})个答案。这时候范围已经小很多了，再进一步筛选就是了。
比赛时就打了这种方法。
但是时间不够，致使很多地方没有调试出来，于是挂了。
比赛之后发现被卡到飞起，甚至不如暴力……
根号算法超过十万从来不靠谱
正解
正解是一种比较有趣的套路。
先接触一下“绝对众数”这个概念。“绝对众数”就是出现次数超过其它不同的数出现次数总和的数，更简单地定义，就是出现次数大于等于(frac{n}{2})的数。
有个很好玩的性质：在数列中删去两个不同的数，那么这个数列的“绝对众数”不变（保证“绝对众数”存在的情况下）。
证明：假如这两个数都不是绝对众数，显然可证；假如其中一个是绝对众数，设绝对众数，出现次数为(k)，满足(kgeq frac{n}{2})，那么对于剩下的区间，也满足(k-1geq frac{n-2}{2})
那么考虑如何在(O(n))的时间内求出区间的绝对众数。设待选的绝对众数为(m)，出现次数为(k)。从左到右扫一遍，对于新加进来的(a_i)：
若(k=0)，则令(m=a_i)，(k=1)
若(m=a_i)，则(k++)
若(m
eq a_i)，则同时删去一个(m)和一个(a_i)，也就相当于(k--)
现在用线段树来维护：对于某个区间，维护绝对众数和它出现的次数，合并的时候假如绝对众数相等，那么出现的次数相加；否则取出现次数较多者，出现次数作差。
感觉改成线段树之后似乎有点怪怪的。考虑从另一个角度证明：两个区间((m_0,k_0))和((m_1,k_1))合并在一起的时候，若(m_0
eq m_1)，相当于(k_0)和(k_1)不断抵消，直到其中一个为(0)为止。区间的绝对众数不可能被其它的数抵消掉，所以区间合并之后最终的(m)就是区间众数。
不过，不管是普通的(O(n))还是线段树，都要保证存在绝对众数才可以保证其正确性，否则算出来的东西什么都不是。不过这里良心地给了SPJ，所以就不需要考虑这个问题。
接下来推广到这一题。
设(q=lfloor frac{1}{p}
floor)，我们要保留最多(q)个答案（姑且叫它(p)众数）
可以用类似的思想，如果删去(q)个不同的数，那么(p)众数是不变的。
为了适应这题，我们一直保留(q)个不同的数。当合并两个区间时，先将一样的(p)众数合并。如果剩下的数超过(q)，那就将所有数的出现次数减一（这时候至少同时消掉(q+1)个不同的数），一直到剩下的数的个数小于等于(q)为止。
对于(p)众数，它减一的时候，总数至少减去(p+1)。当总数被抵消完的时候，它也不会被抵消完。
线段树维护一下区间的(p)众数。合并区间就用上述方法来合并，修改就不用说了。
于是这题就可以非常舒服地解决了，时间复杂度(O(mq^2lg n))
总结
代码没写，马上去实现。
这个方法最妙的地方，我认为是它利用了放宽的限制，用一种看起来正确性很不显然的但又可以证明的方法，计算出我们需要的东西。