<commit_before><commit_msg>Little Elephant and Array - 220B - Codeforces<commit_after>#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int inf = 1e9;

int sq;
struct query {
    int l, r, id;
    query(int a, int b, int c) {
        l = a, r = b, id = c;
    }

    bool operator< (const query& a) const {
        int x = l / sq;
        int y = a.l / sq;
        if (x == y) return r < a.r;
        return x < y;
    }
};

vector<query> queries;
int a[100100];
int ans[100100];
int freq[100100];
int cur = 0;
int n, m;

void add(int x) {
    if (x > n) return;
    if (freq[x] == x)
        cur--;
    freq[x]++;
    if (freq[x] == x)
        cur++;
}

void rm(int x) {
    if (x > n) return;
    if (freq[x] == x)
        cur--;
    freq[x]--;
    if (freq[x] == x)
        cur++;
}


int main(void) {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sq = (int) sqrt(n);
    for (int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        queries.push_back(query(l, r, i));
    }
    sort(queries.begin(), queries.end());
    // l    -> the first index in current range
    // r    -> the last index in current range
    int l = 1, r = 0;
    for (int i = 0; i < queries.size(); i++) {
        int cl = queries[i].l, cr = queries[i].r;
        // add and remove according to range constraints
        while (r < cr)
            add(a[++r]);
        while (r > cr)
            rm(a[r--]);
        while (l < cl)
            rm(a[l++]);
        while (l > cl)
            add(a[--l]);
        ans[queries[i].id] = cur;
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
}

{'fraction_non_alphanumeric': 0.19167643610785462, 'fraction_numerical': 0.01817116060961313, 'mean_word_length': 1.6755485893416928, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7584864', 'n_tokens_mistral': 695, 'n_tokens_neox': 664, 'n_words': 211}