晚上突然颓废了...写什么都写不下,所以就整理一下资料.....
学习了下莫队算法,把能找到的一些链接留一下把.... 首先说说莫队算法是干什么的,貌似就是可以离线做区间无修改询问复杂度为O(Nsqrt(n))的东西。然后这一个的保证就是假设咱们得到了[l,r]的答案,那么咱们通过[l,r]的答案可以在O(1)的时间内得到[l,r+1]&&[l+1,r]&&【l-1,r]&&[l,r-1]的答案的话,那么就可以用莫队做(不管询问到底是什么乱七八糟的东西)(其实不是O(1)的话也可以,比如O(logn),只不过复杂度变成了O(Nsqrt(N)logn))(这个实际上就是需要一个数据结构支持插入删除元素并迅速得到整体信息)
首先是比较正宗的莫队算法的东西,待会儿还会提到一个替代品。(话说询问一些神犇貌似用那个替代品就可以了吧?)
(实际上感觉比较实用的下面这个就可以了,原文附赠了一个地址)
一些基本的性质和证明以及算法都已经提到了,而且还附赠了huzecong神犇的原文地址233。
然后讲一下做法...咱们先用x-y坐标和y=x以及y=-x将平面分割成8个区域。
由于对称性只需要考虑其中四个区域即可。然后假设考虑Y轴正半轴向右45°的区域。设一个点(x1,y1),原点为(x0,y0),那咱们有 x1>=x0,y1-x1>=y0-x0,而曼哈顿距离就是 (x1+y1)-(x0+y0),实际上就是对于每一个点求 (x1+y1)最小的。这个咱们可以先按x从大到小,再按y从大到小排序,然后离散化之后用树状数组做。然后怎么做呢?
咱们用树状数组维护,其中c[i] 表示的是倒序离散化后的x[i]-y[i]的 [i-lowbit(i)+1,i]中的xi+yi最小的。然后直接查询连边即可,然后跑kruskal即可得到曼哈顿距离MST。
然后再在这个曼哈顿距离的MST上遍历即可,一次选择一个没有遍历的节点遍历,然后每次找到一个没有遍历的点就从上一个暴力得到答案的点的答案暴力得到该点的答案,可以证明这样暴力的复杂度是O(Nsqrt(N))的。
然后就是替代品了,那就是分块,咱们把询问 按左端点所在的块为第一关键字,右端点为第二关键字排序,然后暴力搞就可以了,曼哈顿生成树都不需要。
关于分块复杂度为什么可以保证是O(Nsqrt(N))的证明看ydc神犇的题解即可。在此Orz~~。
然后就是莫队算法的一些题目...现在只知道这里有四道....
不过入门的话这几道应该够了吧?
另外百度莫队算法还可以找到一个帖子,里面有关于莫队算法的讨论,看着各种orz啊
评论