[SDOI2009]HH的项链

发表于 | 分类于

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入输出格式

输入格式：

第一行：一个整数N，表示项链的长度。

第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。

第三行：一个整数M，表示HH 询问的个数。

接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

输出格式：

M 行，每行一个整数，依次表示询问对应的答案。

输入输出样例

输入样例#1：
6
1 2 3 4 3 5
3
1 2
3 5
2 6
输出样例#1：
2
2
4

说明

数据范围：

对于100%的数据，N <= 50000，M <= 200000。

分析

这题开始本来是打算用玄学线段树染色过的
然而，贝壳编号数与n的差距，显然是过不了的

这里用的是离线做法
记录pre与now两个数值，pre[i]指i点向后最近的与它编号相同的，now[c]指c编号贝壳的最前一个（有点像链式前向星）
然后以查询左边界排序 维护查询区间内存在唯一单种编号
查询自然是用树状数组

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    int l,r;
    int id;
}ask[404040];
int n,m;
int a[101010],s[101010],ans[404040];
int now[1010101],pre[101010];
inline void read(int &x)
{
    int data=0,w=1;
    char ch=0;
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') w=-1,ch=getchar();
    while (ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^'0'),ch=getchar();
    x=data*w;
}
bool cmp(node u,node w)
{
    return u.l<w.l || (u.l==w.r && u.r<w.r);
}
int bitset(int x)
{
    return x&-x;
}
void add(int x)
{
    while (x<=n)
    {
        ++s[x];
        x+=bitset(x);    
    }
}
int find(int x)
{
    int ans=0;
    while (x)
    {
        ans+=s[x];
        x-=bitset(x);
    }
    return ans;
}
int main()
{
    read(n);
    for (int i=1;i<=n;++i)
        read(a[i]);
        
    for (int i=n;i>=1;--i)    
    {
        pre[i]=now[a[i]];
        now[a[i]]=i;
    }
    for (int i=1;i<=n;++i)
        if (now[a[i]]==i)
        add(i);
    
    read(m);
    for (int i=1;i<=m;++i)
    {
        read(ask[i].l);
        read(ask[i].r);
        ask[i].id=i;
    }
    sort(ask+1,ask+1+m,cmp);
    
    int now=1,x,y;
    for (int i=1;i<=m;++i)
    {
        while (now<ask[i].l)
        {
            if (pre[now]) add(pre[now]);
            ++now;
        }
        if (ask[i].l!=ask[i-1].l)
            x=find(ask[i].l-1);
        y=find(ask[i].r);
        ans[ask[i].id]=y-x;
    }
    for (int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
        
    return 0;    
}
--------------------------