有一个数列，长度最大为 $10^5$ ，每个数字的范围为 $10^9$ 。现在有 `Q` 个询问（ $1 \leqslant Q \leqslant 10^5$ ），每个询问是一个区间，你需要输出这个区间内每个数字出现的次数的立方和。 　　比如说下面的这个数列： > 1 1 3 1 3 1 3 3 　　其中 `1` 出现了 4 次， `3` 也出现了 4 次，那么立方和就是： > $4^3+4^3=128$。 　　这题主要是用分段的思想来做的。 　　首先我们先考虑一种暴力的离线做法： * 求出第一个询问的立方和，存起来。 * 然后一一去不断移动询问的左端点和右端点来做每一个询问。 　　比如上面的数列，我们设第一次询问为 `1~4` ，第二次询问为 `2~5` 。那么我们先暴力做出 `1~4` 的结果为 `28` ，并记录每个数字出现的次数（离散化）。然后做 `3~5` ，在这里我们左端点移动两格；在第一格移动的时候，去掉一个 `1` ，那么 `1` 的数量从 `3` 变为 `2` ，即 $28-3^3+2^3=9$ ；然后移动第二格的时候，又去掉一个 `1` ，那么 `1` 的数量从 `2` 变为 `1` ，即 $9-2^3+1^3=2$ ；最后右端点往右移动一格，即多了一个 `3` ，那么就是 $2-1^3+2^3=9$ ，这就是 `3~5` 的答案了。 　　我们来算下时间复杂度吧，一共有 `Q` 个询问，每个询问我们左右端点最多移动 `N` 次左右，所以时间复杂度差不多就是 $O(NQ)$ ，其中 `N` 和 `Q` 都为 $10^5$ 。 　　这肯定要超时的。但为什么我还要介绍这个暴力的做法呢？ 　　因为下面的正解就是建立在这样的暴力的基础上的。 　　我们将这个数列分段——每段长度为 $\sqrt{N}$ （当然最后一段长度可能比这个小），一共 $\sqrt{N}$ 段。 　　然后我们所有询问分组——所有左端点在同一段的询问分为一组。 　　接下去我们对每一组的询问进行排序——按右端点正序排序。 　　我们现在就可以用之间讲的暴力的做法来做这个题目了。 　　也许有些人会感到奇怪，为什么这么一弄之后就可以了呢？好，让我们再分析一下分段之后的暴力时间复杂度： 　　首先对于每一组询问来说，左端点都在同一段内，而一段的长度不超过 $\sqrt{N}$ ，所以对于左端点的询问时间复杂度为 $O(Q\sqrt{N})$ 。 　　其次对于每一组询问来说，右端点是递增的，所以不管有多少询问，右端点的总步数肯定是在 `N` 以内，然后最多有 $\sqrt{N}$ 组，那么右端点的询问时间复杂度为 $O(N\sqrt{N})$ 。 　　两者一结合，时间复杂度就是 $O((N + Q)\sqrt{N})$ 。非常巧妙有木有？这样一分段就将一个 $O(NQ)$ 的时间复杂度简化到了 $O((N + Q)\sqrt{N})$ 了。