Codeforces - 220B Little Elephant and Array（莫队模板题）

题意：

　　m次查询。每次查询范围[L,R]中出现次数等于该数字的数字个数。

题解：

　　　由于分块，在每次询问中，同一块时l至多移动根号n，从一块到另一块也是最多2倍根号n。对于r，每个块中因为同一块是按y排序，所以最多移动根号n；一共根号n个块。注意l和r要分开考虑。

　　　要注意的是这道题需要离散一下数据。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <cstring>

using namespace std;

const int maxn = 1e5+;

int n, m;

int l, r;

int a[maxn], b[maxn], d[maxn];

int blk;

int blg[maxn];

int ans;

int sum[maxn];

int out[maxn];

struct node {

    int x, y, id;

}c[maxn];

bool cmp(node u, node v) {

    return (blg[u.x]==blg[v.x])?u.y<v.y:u.x<v.x;

}

void update(int x, int t) {

    sum[d[x]] += t;

    if(sum[d[x]] == a[x])

    ans++;

    else if(sum[d[x]] == a[x]+t)

    ans--;

}

int main() {

    while(~scanf("%d%d", &n, &m)) {

        for(int i = ; i <= n; i++) {

            scanf("%d", &a[i]);

            b[i] = a[i];

        }

        sort(b+, b+n+);

        int num = unique(b+, b+n+)-b;

        for(int i = ; i <= n; i++) d[i] = lower_bound(b+, b+num+, a[i])-b;

        blk = sqrt(n);

        for(int i = ; i <= n; i++) blg[i] = (i-)/blk+;

        for(int i = ; i <= m; i++) {

            scanf("%d%d", &c[i].x, &c[i].y);

            c[i].id = i;

        }

        sort(c+, c+m+, cmp);

        l = ; r = ;

        ans = ;

        memset(sum, , sizeof(sum));

        for(int i = ; i <= m; i++) {

            while(l < c[i].x) update(l++, -);

            while(l > c[i].x) update(--l, );

            while(r < c[i].y) update(++r, );

            while(r > c[i].y) update(r--, -);

            out[c[i].id] = ans;

        }

        for(int i = ; i <= m; i++) printf("%d\n", out[i]);

    }

    return ;

}