由于&R闲着无聊，今天上午学习的莫队也并不是完全掌握，老师才发的PPT也没有保存，于是决定乱写一篇靠着自己的理解写一篇关于莫队用法的博客......如果有错的麻烦之处，纯属&R自己理解有问题哈。
一.莫队的含义
莫队是在一篇国家集训队的论文中被提出的。本文只讨论普通的莫队用法。
莫队其实就是一种比较优雅的暴力算法，它只能支持离线计算，时间复杂度为
其中操作的具体方法是，将需要操作的数列，按一定规则排序，规定左端点和右端点，然后将每次计算数列值的时候将左端点和右端点移到目标点上，边移动遍计算。这样的好处是可以避免一些重复计算，这样说可能有亿点点抽象，我们还是先来看一下一些关于莫队的具体操作吧。如果看不懂，我们可以先看第三大点的例题，结合起来看。是复习的话当我没说
二.莫队的基本操作
由于写作水品不加，于是决定先甩一堆模板
1.添加点
void add(int i)
{if(cnt[a[i]] == 0) cur ++ ;cnt[a[i]] ++ ;
}2.删除点
void del(int i)
{cnt[a[i]] -- ;if(cnt[a[i]] == 0) cur -- ;
}3.bool排序
（1）未优化
bool cmp(Node a, Node b)
{int Num = sqrt(n) ;return (a.l/Num != b.l/Num)?a.l<b.l:a.r<b.r ;
}（2）奇偶优化
bool cmp(Node a, Node b)
{int Num = sqrt(n) ;return (a.l/Num != b.l/Num)?a.l<b.l:((a.l/Num)&1)?a.r<b.r:a.r>b.r ;
}备注：！=可以改成^（这样更快），&的等于% 2 == 1。
4.移点的具体操作
void Moteam()
{for(int i = 1; i <= m; i ++){while(l < P[i].l) del(l ++) ;while(r < P[i].r) add(++ r) ;while(l > P[i].l) add(-- l) ;while(r > P[i].r) del(r --) ;ans[P[i].id] = cur ;}
}备注：因为是离线操作，所以拍完序后顺序会被打乱，我没输出时必须还是要按原来的顺序输出，所以需要保存每个点原先进来的id
三.例题
茫然的我于是决定写几道例题来看看，感觉是自己写给自己理解的QAQ
1.HH的项链
(1)题目描述
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。
有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答;因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
(2)输入格式
第一行：一个整数N，表示项链的长度。
第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。
第三行：一个整数M，表示HH 询问的个数。
接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
(3)输出格式
M 行，每行一个整数，依次表示询问对应的答案。
(4)样例
样例输入
6
1 2 3 4 3 5
3
1 2
3 5
2 6
样例输出
2
2
4(5)数据范围与提示
对于20%的数据，N ≤ 100，M ≤ 1000；
对于40%的数据，N ≤ 3000，M ≤ 200000；
对于100%的数据，N ≤ 50000，M ≤ 200000；
(6)题目分析
没什么好分析的不就是板子题吗？
我们想想(用莫队想哈，虽然树状数组也能做Ｑ＾Ｑ)，如果我们用正常的超级暴力的想法来做的话，我们就需要先枚举m，然后从左端点开始枚举，枚举到右端点，用一个数组来判断这个数是否是第一次出现，如果是的话，我们就将ans累加，最后输出，清零，进行m操作即可，时间复杂度为O(mn)。
于是我们决定将这个暴力打的优雅一点点。
我们先思考，假设我们计算了1到4的，然后我们又要计算2到5，那么2到4这个部分就会重复计算，还不如令l = 1， r = 4，用cnt[i]来存储i出现的次数，用cur来表示目前一共出现了多少个没有重复的数。那么l向右移动后，”原先那个数“的个数cnt[l(这里的l是还没移动的坐标)]就会减一，如果个数变成零，那么cur随之减少1。r向右移动，如果cnt[Num[r]]==0，那么就说明这个数是第一次出现，cur++。
一共有四种情况，详细见二.1.2.4.
那么这样真的能优化吗？如果左右两个点总是跨度很大，那么我们不如暴力
智慧的前辈们已经替我们解决了这个问题。
我们可以将这一条线分成很多组，经过平衡，分成根号(n)组是最合适的。所以我们尽量控制左端点在根号n的范围内移动，右端点在n的范围内移动，所以就有了二.3.(1)的排序
可是我们还有一种更优的排序方法二.3.(2)
我们思考当第一组（共根号n组）的r移动到最右边时（r是按从左到右排了序的），我们在计算第二组的时候为了让r少跑一点，于是将r从右到左排序，于是就有了奇数组按a.r < b.r, 偶数组按a.r > b.r的排序方法
#include <bits/stdc++.h>
using namespace std ;
const int MAXM = 200005 ;
int n, a[50005], m, cur = 0, cnt[1000005], Num = 1, l = 1, r = 0, ans[MAXM] ;
struct Node
{int l, r, id ;
}P[MAXM] ;
bool cmp(Node a, Node b){return (a.l / Num) != (b.l / Num) ? a.l < b.l : ((a.l / Num) & 1) ? a.r < b.r : a.r > b.r ;
}
int read()
{int x = 0, f = 1 ;char c = getchar() ;while(c < '0' || c > '9'){if(c == '-') f = -1 ;c = getchar() ;}while(c >= '0' && c <= '9'){x = x * 10 + c - '0' ;c = getchar() ;}return x * f ;
}
void add(int i)
{if(cnt[a[i]] == 0) cur ++ ;cnt[a[i]] ++ ;
}
void det(int i)
{cnt[a[i]] -- ;if(cnt[a[i]] == 0) cur -- ;
}
void Moteam()
{for(int i = 1; i <= m; i ++){while(l < P[i].l){det(l ++) ;}while(r < P[i].r){add(++ r) ;}while(l > P[i].l){add(-- l) ;}while(r > P[i].r){det(r --) ;}ans[P[i].id] = cur ;}
}
void Init()
{n = read() ;memset(cnt, 0, sizeof(cnt)) ;Num = (int)sqrt(n) ;for(int i = 1; i <= n; i ++){a[i] = read() ;}m = read() ;for(int i = 1; i <= m; i ++){P[i].l = read(), P[i].r = read(), P[i].id = i ;}sort(P + 1, P + m + 1, cmp) ;
}
int main()
{Init() ;Moteam() ;for(int i = 1; i <= m; i ++){printf("%d\n", ans[i]) ;}
}
