·莫队算法被大家称为“优雅的暴力”

·排序巧妙优化复杂度，带来NOIP前的最后一丝宁静。几个活蹦乱跳的指针的跳跃次数，决定着莫队算法的优劣……

·目前的题型概括为三种：普通莫队，树形莫队以及带修莫队。

照常在这引用两篇我学习莫队的博客

https://www.cnblogs.com/Paul-Guderian/p/6933799.html

https://www.cnblogs.com/RabbitHu/p/MoDuiTutorial.html

 

莫队算法其实是一个非常容易学习的一个算法，它灵活的分块排序让我们的复杂度神奇的降低下来

我在这里只讲述离线莫队

来个题 

Given a sequence of n numbers a₁, a₂, ..., a_n and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence a_i, a_i+1, ..., a_j.

Input

• Line 1: n (1 ≤ n ≤ 30000).
• Line 2: n numbers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁶).
• Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
• In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).

Output

• For each d-query (i, j), print the number of distinct elements in the subsequence a_i, a_i+1, ..., a_j in a single line.

   

Example

Input51 1 2 1 331 52 43 5Output323 题意：求区间内的不同数字个数； 解法： 第一步：本来如果我们使用纯暴力，每个都遍历的话，n范围10^4,有q次查询，范围10^5，然后我们遍历左区间到右区间又是n10^4 完美的10^13,大爆炸， 第二步：然后我们想怎么去优化，想想能不能利用之前的查询结果，就像尺取法，每次只是更新移动左右端点，我们试试 我们开始保存了1 5的结果，用个数组记录这个区间的出现的数及其次数，然后我们在移动左右端点的时候，只要判断这个数的次数减去一个之后是否为零 加的时候，之前是否为0，就能加减这个区间不同数字的个数，但是我们又想一下，如果他的查询是1 N 然后 （1+n）/2,(1+n)/2....使每次的端点移动 步数最大，那我们之前做的优化相当于没做， 第三步：那我们是否可以使我们查询的波动小一点呢，答案是可以的，我们只要改变查询的顺序，使每次的端点移动步数 尽量的小即可，那我们就有一个固定的排序方法，“分块”，我们把n分成“根号n”块，给每个块加个编号， 然后我们排序方式：在我们m次查询中，编号小的在前，如果同在一个块内，右端点小的在前 以上第二步+第三步就是我们神奇的莫队，核心思想：利用前面查询的结果，然后我们移动端点的次数尽量少，分块的个数是根号n 因为左端点是以根号n分块的，所以两个区间最多相差一个块，右端点可以从1到n所以复杂度是O(n*根号n) 然后我们理解莫队就可以敲这个题了

#include
       
        #include
        
         #include
         
          #define B 174 //根号30000 #define bel(x) ((x - 1) / B + 1) //求一个区间在第几个块using namespace std;struct sss{    int id;    int left,right;    friend bool operator <(struct sss x,struct sss y)//莫队排序方法    {        return bel(x.left)==bel(y.left)?x.right
          
           y.left;    }}q[200001];int cnt[1000001];int a[30001];int b[200001];int sum=0;void del(int x){    cnt[x]--;    if(!cnt[x]) sum--;}void add(int x){    if(!cnt[x]) sum++;    cnt[x]++;}int main(){    int n;    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        scanf("%d",&a[i]);    }    int m;    scanf("%d",&m);    for(int i=1;i<=m;i++)    {        q[i].id=i;        scanf("%d%d",&q[i].left,&q[i].right);    }    sort(q+1,q+m+1);    int l=1,r=0;    for(int i=1;i<=m;i++)    {        while(l
           
            q[i].left) add(a[--l]);        while(r
            
             q[i].right) del(a[r--]); b[q[i].id]=sum; } for(int i=1;i<=m;i++) { printf("%d\n",b[i]); }}