SPOJ DQUERY - D-query （莫队算法）

Given a sequence of n numbers a1, a2, ..., an 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 ai, ai+1, ..., aj.

Input

• Line 1: n (1 ≤ n ≤ 30000).
• Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 106).
• 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 ai, ai+1, ..., aj in a single line.

Example

Input
5
1 1 2 1 3
3
1 5
2 4
3 5

Output
3
2
3

题意：有n个数，m个询问，每次询问l，r区间内有多少个不同的数。

这题作为莫队算法的入门题再好不过了，我们就借这题来讲解一下莫队算法。

莫队算法是用来解决离线查询的一种算法，主要思想就是借助前一次查询的结果，把区间向左向右伸缩推出下一个查询的结果。

利用两个指针分别指向区间的左端点和右端点，然后通过左移或者右移指针得到下一个区间的答案。

当然直接按询问的循序来进行指针的跳跃肯定是不行的，这样的复杂度最终会达到n^2，我们得采取一点技巧：

我们可以把整个区间分成一个一个块（每块大小为sqrt(n)，一共有W块，W = n/sqrt(n)），然后先按照询问左端点所属的块数从小到大排序，如果所属块数相同，那么再按右端点大小从小到大排序，这样复杂度就降了下来。

我们来计算一下复杂度：

先看左端点，如果上次询问的左端点和这一次的左端点在同一个块，那么最多只要移动sqrt(n)次，如果不在一个块，最多要移动n次，这样m个询问一平均，就是常数了，所以左端点平均为sqrt(n)次

右端点：右端点只有在左端点在同一块内的时候才是有序的，其他的时候是不可控制的，所以右端点每次最坏情况是移动n次，

但是这种情况只会发生 W 次，可以把n，m看成同一级的，所以右端点的复杂度 n*n/sqrt(n)

所以总复杂度就为O（n*n/sqrt(n)） 即 O （n^(1.5)）

有了上面的思想之后，其实代码还是比较简单的，主要部分就四个while，用来伸缩左右端点。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long

using namespace std;


struct query
{
    int id,l,r,ans;
}q[200010];

int a[30010];
int f[1000010];
int W;
int cnt;

int li(int x)
{
    return (x-1)/W + 1;
}
bool cmp1(query a,query b)
{
    if(li(a.l) == li(b.l))
        return a.r < b.r;
    return a.l < b.l;
}

bool cmp2(query a,query b)
{
    return a.id < b.id;
}

void add(int x)
{
    f[a[x]]++;
    if(f[a[x]] == 1)
        cnt++;
}

void del(int x)
{
    f[a[x]]--;
    if(f[a[x]] == 0)
        cnt--;
}
int main(void)
{
    int n,m,i,j;
    while(scanf("%d",&n)==1)
    {
        W = sqrt(n);   //块的大小
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].id = i;
        }
        sort(q+1,q+m+1,cmp1);
        memset(f,0,sizeof(f));
        int l = 1,r = 0;
        cnt = 0;
        for(i=1;i<=m;i++)
        {
            while(r < q[i].r) add(++r); //添加右端点
            while(r > q[i].r) del(r--); //删除右端点
            while(l < q[i].l) del(l++); //删除左端点
            while(l > q[i].l) add(--l); //添加左端点
            q[i].ans = cnt;
        }
        sort(q+1,q+m+1,cmp2);
        for(i=1;i<=m;i++)
            printf("%d\n",q[i].ans);
    }

    return 0;
}