※ 引述《GYLin (Lynx)》之铭言：
: 大致策略:
: 1. 把途中所有累积加值都模100000, 原因很明显
: 2. 当需要计算Sum[L,R]时, 其值为"不考虑爆掉的原本加总"扣掉100000*(区间内爆掉人数)
: 爆掉人数为: 区间内的Ai个数, 其值加上目前累积加值会超过100000的人们
: 要计算爆掉人数, 只要维护一个 Map[i][j] 就可以,
: Map[i][j] 就是 阵列 1~i, 加上高度 j 会爆掉的人数,
: 若开普通阵列可能需要 100000*100000 的大小,
: 但实际上出现的询问只会有 10^6 种,
: 所以先把询问全部存起来后, 再针对会出现的询问求出爆掉人数,
: 再回去把存起来的询问解决即可.
另一种可以 online 的作法(不用预处理询问)
在每次的询问，
假设不会爆掉，我们只要知道原始的 aL + ... + aR 再加上 K * (R - L + 1) 就是
答案。这个部份只要先算出原始 a_i 的前缀和就可以做到。
而每爆掉一个，答案就需要减掉 10^5，
因此我们想知道 aL ~ aR 中高度不超过 10^5 - K 的有几个。
假设我们有一个 binary search tree, 里面的点是 {i | ai <= 10^5 - K}
那我们可以在 O(lg n) 的时间知道 |{i | ai <= 10^5 - K} ∩{L...R}|
问题是我们要做出 10^5 个 BST，这样好像会 OOM 或 TLE
再想一下会发现：
BST[0] = empty tree
BST[i] = BST[i - 1] + {j | aj == i}
也就是从 BST[0] 到 BST[10^5] ，只会有 n 个 insert
如果我们做 copy on write 的话，我们可以让每次的 insert 都只多用 O(lg n) 的空间，
时间也还是 O(lg n)
于是，我们有：
time complexity of pre-processing: O(n lg n)
space complexity: O(n lg n)
Time complexity of each query: O(lg n) + O(1) (BST query + prefix sum)
Overall time complexity: O(m lg n + n lg n)