wy今天学习了分块算法and莫队算法。。。
写一份萌萌哒的日志。。。
先说分块算法。。。
这是在线的算法。。。
我们将长度为n的序列分为√n个小块，对于每个询问区间l,r，有些块是完全包含其中的，有些块是部分包含的。。。
对于完全包含其中的块，我们可以预处理出答案，对于部分包含的块，我们可以暴力求解，这样，每次询问的复杂度即为O(n√n)。。。
至于修改的操作嘛，我们至多用√n的时间即可解决。。。
该算法的题目有：
BZOJ2724 求区间众数（强制在线）
BZOJ2821 求区间出现正偶数次的数的总数（强制在线）
BZOJ3343 将区间内的数加上X and 求区间内不小于X的数的个数
再来讲莫队算法。。。
这是一个离线算法and不支持复杂的修改操作。。。
也是将长度为n的序列分为√n个小块，对于每个询问区间l,r，以 l所在的块 为第一关键字，r 为第二关键字排序。。。
对于当前询问Que[x].l，Que[x].r ,我们可以以 O(|Que[x].l-Que[x-1].l|+|Que[x].r-Que[x-1].r|) 的复杂度由Que[x-1].l，Que[x-1].r推来，可以证明算法复杂度为 O(n√n)。。。
我们也可以用莫队算法实现简单的修改操作，即建立一个时间轴，将每个询问 l,r,time 以 l所在的块 为第一关键字， r所在的块 为第二关键字,time 为第三关键字排序。。。
每个询问依旧从上一个询问推来，这样的算法复杂度为O(n^2)。。。
该算法的题目有：
BZOJ1878 求区间内出现的数的种数
BZOJ2038 求区间内两数相同的概率
BZOJ3781 求区间内数的出现次数的平方和
评论 (0)
