莫队回滚算法

对被查询数组分块，每块平均长度为Q，把左端点位于同一个块中的查询保存，然后再把这些区间根据右端点排序。这样我们在每个块中就有如下属性，每次进行查询右端点递增，左端点来回摆动。因为每个块中的查询是根据右端点排序的。右端点的查询很好处理，参考滑动窗口的做法，但是左端点的来回摆动就需要分为添加和删除的操作了。如果我们维护了一个关于数字和次数的表，每次去进行查询的复杂度显然是n，那么用一个数据结构（平衡树之类）进行查询的复杂度为logn。这也太大了，所以我们考虑不使用删除操作，而改为回滚，每次都从块0——块1边界（这里以块0的查询为例，在这个例子中右边界位于块0中直接暴力，所以考虑的例子都是有边界大于块0的）开始把从查询左边界到块0的值都加一遍，然后计算结果，然后把这次查询的值全减掉，继续下一次查询这样每次左边界状况都还原到了没有进行查询的状态。