前话

      有时候我们对于一些区间求解问题，总是想不到什么方法去解决。

      有人说线段树来记录状态，但是使用线段树是状态的转移就不能是O（1）。这时候线段树就没有了自己的优势，如 [国家集训队]数颜色 一题。用线段树维护则显得麻烦。

正题

      所以，我们在这里引入一种新算法：莫队。

      传说能解决一切区间问题的算法（优雅的暴力）

      我们尝试着用暴力来做一下此题[国家集训队]数颜色。

      当然就是每次询问区间，就把这段区间过一下，如果有新的颜色，就ans++。输出答案。

      我们在这个过程中可以发现，我们好像做多了好多冗余的操作。

      例如重复算两段相同的区间，或者算两段有交集的区间。如下图，我们会把红色部分算两次。

      没错，我们当然就想到了用区间转移的方法。

      如果当前(x1,y1)已经处理完毕，我们只需把y1移到y2，加上这段区间的新颜色，x1移到x2，删去这段区间只出现过一次的颜色。

      如果当前(x2,y2)已经处理完毕，我们只需把x2移到x1，加上这段区间的新颜色，y2移到y1，删去这段区间只出现过一次的颜色。

      但是这样做的最差时间复杂度还是很高，一次移动需要n，那么m次移动就需要m*n.

      我们试着排序。（按左端点为第一关键字，右端点位第二关键字）

      还是有极端情况，如(1,1),(1,50000),(2,2),(2,50000)...

      那么这样状态转移，1次也需要n。

      在此引入一种很强的优化：分块

      我们总是习惯于给公式的值分块，但区间分块还是第一次见吧。

      我们把整个区间分为sqrt n块，那么每块的大小都是sqrt n，为什么？方便均摊时间复杂度从而达到最优解。

      那么我们怎么利用分块？？

      当然，在排序上用。

      1.对于在同一个块的左端点，按照右端点从小到大排序。

      2.对于不再同一个的左端点，按照左端点从小到大排序。

      这时候我们就会发现，时间复杂度大大降低了。

      对于左端点在同一个块的区间，左端点的总转移时间复杂度为O(sqrt(n)),右端点的转移时间复杂度为O(n).

      而对于左端点不再同一个块的区间，左端点的总转移时间复杂度为O(2*sqrt(n)),右端点的转移时间复杂度为O(n);

      那么我们有sqrt(n)个块，所以我们的时间复杂度就是sqrt(n)*(sqrt(n)+n)=n+sqrt(n)*n;

      暴力就是这样被我们优化到了n*sqrt(n)!!!!!