莫队算法是用来骗分的……这个算法的使用前提是

在不强制在线的情况下，对于[l,r],[l',r']的区间询问，我们需要要O(|l-l'|+|r-r'|)次基本操作从[l,r]转移得到[l',r']的答案

可以发现这就是个高能暴力，只不过因为转移方向的优越带来比裸暴力更优的时空复杂度

如果说cdq分治是花费了复杂度干掉了在线，那么莫队就是花费复杂度干掉了区间

对于所有的询问，把当前询问包含的元素叫作当前的处理集合，然后暴力转移维护处理集合来解决下一个区间的询问

首先是最基本的：序列上应用莫队

现在流行的做法是分块，先分成sqrt(n)个块，我们把每个询问按照左端点所在块的编号作为第一关键字，右端点作为第二关键字排序

按这个顺序暴力转移，考虑两种情况

1. 相邻询问第一关键字相等等于x，这样由于第二关键字是递增的，所以所有第一关键字等于x的询问处理总的复杂度是O(n*转移所需复杂度)的，由于第一关键字最多sqrt(n)种取值

2. 第一关键字不等，那么相邻询问转移是O(n*转移所需复杂度)的，但是这样的情况最多出现O(sqrt(n))

所以可以证明复杂度=O(nsqrt(n)*转移所需复杂度)

简单例题：bzoj2038,bzoj3781由于太水我就不放代码了

例题：bzoj3809 比上面稍微难一点，由于颜色也有区间，所以我们可以考虑再对美丽度分块，这样就可以快速统计了，复杂度为O((m+n)sqrt(n)）

下面是比较难的：树上莫队

树怎么分块？请见bzoj1086手把手教树分块，我是orz vfk的分块方式的

树上分块之后，我们就可以树上莫队了

但是等等，不对啊，树上的路径询问怎么转移？

这里我们引入一个东西叫做对称差，说白了就是异或（在处理集合的存在性取反）

我们设S(x,y)代表x,y之间路径的处理集合,h(x)代表节点x的元素

显然对于询问[x,y]，处理集合S(x,y)=S(x,root) xor S(y,root) xor h(lca(x,y));

现在考虑转移到询问[x',y]（先转移x，y类似）,考虑lca只有一个元素，我们可以最后处理

定义T(x,y)=S(x,root) xor S(y,root)

则T(x',y)=S(x‘,root) xor S(y,root)=S(x',root) xor S(x,root) xor S(x,root) xor S(y,root)=T(x',x) xor T(x,y)

所以我们只要把x',x路径上的点存在性取反即可，然后就没了

这里排序有个小技巧，对于询问[x,y]把节点x所在块标号大于y的编号则交换x,y

简单例题：bzoj3757 太水了我就不放代码了

下面是最变态的了：树上带修改莫队

莫队是可以带修改了，学过cdq分治后不难想到把操作时间作为第三关键字排序，这样就搞定了

每次我们不仅要转移询问，还要让处理时间，还是要利用时间戳

注意这里出现了三个关键字，这里证明时间复杂度不难发现分块的大小是n^(2/3)最优,这样复杂度强行O(n^(5/3))，证明的话我就懒得写了

例题：bzoj3052 我很良心的放一个代码

1 type way=record  2        po,next:longint;  3      end;  4      node=record  5        x,y,id:longint;  6      end;  7   8 var e:array[0..200010] of way;  9     q,op:array[0..100010] of node; 10     anc:array[0..100010,0..20] of longint; 11     d,p,pre,last,prim,st,be,c,w,s,v:array[0..100010] of longint; 12     f:array[0..100010] of boolean; 13     ans:array[0..100010] of int64; 14     test,size,i,j,n,m,x,y,ch,len,t,cur,t1,t0:longint; 15     now:int64; 16 procedure add(x,y:longint); 17   begin 18     inc(len); 19     e[len].po:=y; 20     e[len].next:=p[x]; 21     p[x]:=len; 22   end; 23  24 procedure dfs(x:longint); 25   var i,y,h:longint; 26   begin 27     h:=t; 28     i:=p[x]; 29     while i<>0 do 30     begin 31       y:=e[i].po; 32       if y<>anc[x,0] then 33       begin 34         anc[y,0]:=x; 35         d[y]:=d[x]+1; 36         dfs(y); 37         if t-h>=size then 38         begin 39           inc(len); 40           while h<>t do 41           begin 42             be[st[t]]:=len; 43             dec(t); 44           end; 45         end; 46       end; 47       i:=e[i].next; 48     end; 49     inc(t); 50     st[t]:=x; 51   end; 52  53 procedure swap(var a,b:longint); 54   var c:longint; 55   begin 56     c:=a; 57     a:=b; 58     b:=c; 59   end; 60  61 function cmp(a,b:node):boolean; 62   begin 63     if (be[a.x]=be[b.x]) and (be[a.y]=be[b.y]) then exit(a.id
      
       j) then 79       begin 80         y:=q[i]; q[i]:=q[j]; q[j]:=y; 81         inc(i); 82         dec(j); 83       end; 84     until i>j; 85     if l
       
        q[i].id do111     begin112       if f[op[cur].x] then del(c[op[cur].x]);113       if pre[cur]=0 then c[op[cur].x]:=prim[op[cur].x]114       else c[op[cur].x]:=op[pre[cur]].y;115       if f[op[cur].x] then ins(c[op[cur].x]);116       dec(cur);117     end;118   end;119 120 procedure rev(x:longint);121   begin122     if not f[x] then ins(c[x])123     else del(c[x]);124     f[x]:=not f[x];125   end;126 127 procedure work(x,y:longint);128   begin129     while x<>y do130     begin131       if d[x]>d[y] then132       begin133         rev(x);134         x:=anc[x,0];135       end136       else begin137         rev(y);138         y:=anc[y,0];139       end;140     end;141   end;142 143 function lca(x,y:longint):longint;144   var i:longint;145   begin146     if x=y then exit(x);147     if d[x]
        
         d[y] then149     begin150       for i:=trunc(ln(d[x])/ln(2)) downto 0 do151         if d[x]-1 shl i>=d[y] then x:=anc[x,i];152     end;153     if x=y then exit(x);154     for i:=trunc(ln(d[y])/ln(2)) downto 0 do155       if anc[x,i]<>anc[y,i] then156       begin157         x:=anc[x,i];158         y:=anc[y,i];159       end;160     exit(anc[x,0]);161   end;162 163 procedure get(i:longint);164   var z:longint;165   begin166     z:=lca(q[i].x,q[i].y);167     rev(z);168     ans[q[i].id]:=now;169     rev(z);170   end;171 172 begin173   readln(n,m,test);174   size:=0;175   while size/n*size/n*size<1 do inc(size);176   dec(size);177   for i:=1 to m do178     read(v[i]);179   for i:=1 to n do180     read(w[i]);181   for i:=1 to n-1 do182   begin183     readln(x,y);184     add(x,y);185     add(y,x);186   end;187   len:=0;188   dfs(1);189   while t>0 do190   begin191     be[st[t]]:=len;192     dec(t);193   end;194   for j:=1 to trunc(ln(n)/ln(2)) do195     for i:=1 to n do196     begin197       x:=anc[i,j-1];198       anc[i,j]:=anc[x,j-1];199     end;200   for i:=1 to n do201   begin202     read(c[i]);203     prim[i]:=c[i];  //初始颜色204   end;205   for i:=1 to test do206   begin207     readln(ch,x,y);208     if ch=0 then209     begin210       inc(t0);211       op[t0].x:=x; op[t0].y:=y; op[t0].id:=i;212       pre[t0]:=last[x];213       last[x]:=t0;  //记录上一个关于点x的操作，方便解决时间倒流214     end215     else begin216       inc(t1);217       q[t1].x:=x; q[t1].y:=y; q[t1].id:=i;218       if be[q[t1].x]>be[q[t1].y] then swap(q[t1].x,q[t1].y);219     end;220   end;221   sort(1,t1);222   timec(1);223   work(q[1].x,q[1].y);224   get(1);225   for i:=2 to t1 do226   begin227     timec(i);228     work(q[i-1].x,q[i].x);229     work(q[i-1].y,q[i].y);230     get(i);231   end;232   for i:=1 to test do233     if ans[i]<>0 then writeln(ans[i]);234 end.
        
       
      

总之莫队是一个有效的骗分神器，但是他太一般化了，所以一些特殊的问题无法做的更好，尽量不要一上来就写莫队