记录编号	305554	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	3.164 s
提交时间	2016-09-10 21:24:21	内存使用	6.49 MiB

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <cmath>
#include <string.h>
using namespace std;
#define MAXN 50003
#define MAXM 200003
#define MAXC 1000003
int data[MAXN];
struct que
{
    int l, r;
    int ans;
    int id;
    int bid;
    bool operator<(const que &o) const
    {
        return id < o.id;
    }
}qs[MAXM];
bool cmpbyb(const que &q1, const que &q2)
{
    return q1.bid < q2.bid || (q1.bid == q2.bid && q1.r < q2.r);
}
int ans = 0;
int cnt[MAXC];
void rem(int pos)
{
    cnt[data[pos]]--;
    if(cnt[data[pos]] == 0)
        ans--;
}
void add(int pos)
{
    cnt[data[pos]]++;
    if(cnt[data[pos]] == 1)
        ans++;
}
int main()
{
    freopen("diff.in", "r", stdin);
    freopen("diff.out", "w", stdout);
    int n, m;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", data+i);
    scanf("%d", &m);
    int magic = (int)sqrt(n);
    for(int i = 1; i <= m; i++)
    {
        que &q = qs[i];
        scanf("%d %d", &q.l, &q.r);
        q.id = i;
        q.bid = q.l/magic;
    } 
    sort(qs+1, qs+1+m, cmpbyb);
    int cl = 0, cr = 0;
    for(int i = 1; i <= m; i++)
    {
        que &q = qs[i];
        while(cl < q.l)
        {
            rem(cl);
            cl++;
        }
        while(cl > q.l)
        {
            cl--;
            add(cl);
        }
        while(cr < q.r)
        {
            cr++;
            add(cr);
        }
        while(cr > q.r)
        {
            rem(cr);
            cr--;
        }
        q.ans = ans;
    }
    sort(qs+1, qs+1+m);
    for(int i = 1; i <= m; i++)
        printf("%d\n", qs[i].ans);
    return 0;
}