wtf，最近挖坑有点小多啊，没办法>_<容我先把糖果公园A了再来写这个吧= =看看今天能不能A掉好吧，我承认我第二天才把糖果公园A掉>_<下面把这篇小结补上首先众所周知的是莫队算法是要把询问先按左端点属于的块排序，再按右端点排序复杂度就先不证了，有兴趣的同学可以自己YY下或者查阅资料下面举几个例子详细说明
1.小Z的袜子Description:给定一个序列个询问每次询问：区间中选两个数，两个数相等的概率若概率为仔细观察发现，令区间时答案就是假如我们知道表示，用ans表示当前答案那么我们可以考虑当我们从时对ans的影响已知只有这个值的变化影响着我们的答案，而且容易看出答案是想一想为什么其他情况同理请自行思考这样每次转移均是Code2.Codeforces 86D(Yandex.Algorithm 2011)几乎和小Z的袜子一模一样的莫队模板题Code3.bzoj 3289(Mato的文件管理)Description给定一个序列个询问每次询问:区间中逆序对数很显然的发现可以用树状数组+莫队艹过去，每次修改是的，可以通过Code这些题基本上都是一个套路了，学了莫队基本就会了因为每次查询都是一个连续的区间，我们可以轻易找到每移动一次后对答案的贡献那么，如果不是正常的对序列的区间询问，而是对树上两点路径的询问该怎么办呢？没错，这就是传说中的。。。 树上莫队 先举个例子1.Spoj 10707 Count on a tree II(COT2)Description给定一棵树上n个结点上的数值，个询问每次询问:区间中不同值的个数卧槽，这TM怎么做啊？区间不是连续的啊！这莫队是不是做不了啊？莫慌，我们有个神奇的东西，叫做 dfs序我们可以用时间戳来对每个节点进行标记，$l_x$,$r_x$分别表示$x$的进出时间我们利用了dfs序的性质，可以把两点间路径转换为一个连续的区间（还需要考虑Lca的问题，想一想，为什么）没错，这样我们便可以对dfs序进行分块，莫队一样搞！神犇们看到现在的话应该会做了，蒟蒻还是继续详细的说做法把>_<定义路径上的顶点集合，，root表示根节点表示集合中的对称差)定义，我们先不管lca的事情如果我们从的路径的话对答案有什么影响呢？根据定义我们可以得到于是我们可以得到即每次更新时即可也即对v-v’的路径(除了)的点的存在性取反即可实际上我们记录的是统计答案然后再将就行了其实读者可以换个图把dfs序标一下帮助理解>_<然后这题实际已经解决了，将dfs序分块就将区间化为dfs序上区间问题，考虑lca就可以了
Code2.WC 2013 糖果公园(Uoj 58)Description唔。。题目太长了童鞋们自己看吧>_<戳这里总之它是需要修改的啦~好了，想必看到这里，大家对莫队算法和树上莫队算法都已经有了一定的了解我们发现之前我们做的题都是只有查询没有修改，那么有修改的就不可以做了吗？并非如此如果没有修改我们随意搞搞就可以了，有修改的话相等于加了一个时间的维度变成了三维的我们可以按左端点为第一关键字，右端点为第二关键字，时间为第三关键字排序预处理每次修改前的颜色，以及这次修改后的颜色莫队对询问排序每次询问发现与上次时间不同时暴力t++，t–同时修改颜色及答案即可（用到之前预处理）然后解决完时间问题后便就是正常的二维莫队了如果我们将块的大小设为块相当于询问分成了由于n和q同阶，所以总复杂度是所以得到最优然后就是拍代码啦~Code完结撒花！(妈蛋从10点多写到现在总算是写完了，感人肺腑,意识不清可能哪里写错了，多多包涵>_<
后来逐渐有广州花城的，
