Codeforces 220B Little Elephant and Array（莫队）

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
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define for0(i,a,b) for (int i = a; i < b; i++)
#define for1(i,a,b) for (int i = a; i <= b; i++)

using namespace std;

const int N = 1e5+5;
const int M = 1e5+5;
const int MAXV = 1e5+5;

int blo,bl[N],m,n;
int v[N],mp[MAXV];
int sum;
int ans[M];

struct node
{
    int l,r;
    int id;
    bool operator < (const node& a)const{
        if (bl[l]==bl[a.l]) return r < a.r;
        return bl[l] < bl[a.l];
    }
}q[M];

int data[N];
void discrete(int a[],int n)///离散化
{
    for (int i=1;i<=n;i++) data[i] = a[i];
    sort(data+1,data+1+n);
    int cnt = unique(data+1,data+1+n) - data;
    for (int i=1;i<=n;i++) a[i] = lower_bound(data+1,data+1+n,a[i]) - data;
}

void REMOVE(int x)
{
    if (mp[v[x]]==data[v[x]]) sum--;
    mp[v[x]]--;
    if (mp[v[x]]==data[v[x]]) sum++;
}

void ADD(int x)
{
    if (mp[v[x]]==data[v[x]]) sum--;
    mp[v[x]]++;
    if (mp[v[x]]==data[v[x]]) sum++;
}

void solve()
{
    int nowl = 1,nowr = 0;
    for1(i,1,m){
        int tl = q[i].l,tr = q[i].r;
        while (nowr<tr) ADD(++nowr);
        while (nowl>tl) ADD(--nowl);
        while (nowr>tr) REMOVE(nowr--);
        while (nowl<tl) REMOVE(nowl++);
        ans[q[i].id] = sum;//ans[q[i].id] = mp.size();
    }
}

int main()
{
    scanf("%d",&n);
    scanf("%d",&m);
    blo = sqrt(n);
    for1(i,1,n){
        scanf("%d",v+i);
        bl[i] = (i-1)/blo+1;
    }

    discrete(v,n);

    for1(i,1,m){
        scanf("%d %d",&q[i].l,&q[i].r);
        q[i].id = i;
    }
    sort(q+1,q+1+m);

    solve();

    for1(i,1,m){
        printf("%dn",ans[i]);
    }
    return 0;
}