Little Elephant and Array (Codeforces 220B)
Tags: Others, data structures

The Little Elephant loves playing with arrays. He has array a, consisting of n positive integers, indexed from 1 to n. Let's denote the number with index i as ai. Additionally the Little Elephant has m queries to the array, each query is characterised by a pair of integers lj and rj (1 ≤ lj ≤ rj ≤ n). For each query lj, rj the Little Elephant has to count, how many numbers x exist, such that number x occurs exactly x times among numbers alj, alj + 1, ..., arj.Help the Little Elephant to count the answers to all queries.

Input: The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105) — the size of array a and the number of queries to it. The next line contains n space-separated positive integers a1, a2, ..., an (1 ≤ ai ≤ 109). Next m lines contain descriptions of queries, one per line. The j-th of these lines contains the description of the j-th query as two space-separated integers lj and rj (1 ≤ lj ≤ rj ≤ n).

Output: In m lines print m integers — the answers to the queries. The j-th line should contain the answer to the j-th query.


Sample Inputs:
7 2
3 1 2 2 3 3 7
1 7
3 4

Sample Outputs:
3
1

Solution (Python):
import sys

def get_ints():
    return map(int, sys.stdin.readline().split())
(n, m) = map(int, input().split())
arr = list(get_ints())
arr = [0] + arr
summ = [0] * 100001
freq = [0] * 100001
l = [0] * 100001
r = [0] * 100001
for ii in arr:
    if ii <= n:
        freq[ii] += 1
for i in range(1, m + 1):
    (x, y) = get_ints()
    l[i] = x
    r[i] = y
ans = [0] * (m + 1)
for i in range(1, n + 1):
    if freq[i] >= i:
        for j in range(1, n + 1):
            summ[j] = summ[j - 1]
            if arr[j] == i:
                summ[j] += 1
        for k in range(1, m + 1):
            if summ[r[k]] - summ[l[k] - 1] == i:
                ans[k] += 1
for i in range(1, m + 1):
    print(ans[i])

Solution (Python):
import sys
from collections import Counter
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
cnt = Counter(a)
maybe = {}
for (val, c) in cnt.items():
    if c >= val:
        l = len(maybe)
        maybe[val] = l
pref = [[0] * len(maybe)]
for i in range(n):
    pref.append(pref[-1][:])
    if a[i] in maybe:
        pref[-1][maybe[a[i]]] += 1
for _ in range(m):
    (l, r) = map(int, input().split())
    cur = 0
    for (val, c) in maybe.items():
        if pref[r][c] - pref[l - 1][c] == val:
            cur += 1
    print(cur)

Solution (Python):
""""""
import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(N, M, A, Q):
    bit = [0 for _ in range(N)]

    def add(index, val):
        while index < N:
            bit[index] += val
            index |= index + 1

    def query(index):
        index = min(index, N - 1)
        s = 0
        while index >= 0:
            s += bit[index]
            index = (index & index + 1) - 1
        return s
    q = collections.defaultdict(list)
    for (i, (l, r)) in enumerate(Q):
        q[r].append((l, i))
    ans = [0 for _ in range(M)]
    vi = collections.defaultdict(list)
    for (i, v) in enumerate(A):
        u = vi[v]
        u.append(i)
        lv = len(vi[v])
        if lv >= v:
            add(u[-v], 1)
            if lv >= v + 1:
                add(u[-v - 1], -2)
            if lv >= v + 2:
                add(u[-v - 2], 1)
        for (l, qi) in q[i]:
            ans[qi] = query(i) - query(l - 1)
    print('\n'.join(map(str, ans)))

def test():
    (N, M) = (100000, 100000)
    import random
    A = [random.randint(0, 1000) for _ in range(N)]
    Q = []
    for i in range(M):
        l = random.randint(0, N - 1)
        r = random.randint(l, N - 1)
        Q.append((l, r))
    solve(N, M, A, Q)
(N, M) = map(int, input().split())
A = [int(x) for x in input().split()]
Q = []
for i in range(M):
    (l, r) = map(int, input().split())
    Q.append((l - 1, r - 1))
solve(N, M, A, Q)