Little Elephant and Array (Codeforces 221D)
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 os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class query:
    global z

    def __init__(self, l, r, i):
        self.lb = (l - 1) // z
        self.l = l
        self.r = r
        self.ind = i

    def __lt__(a, b):
        return a.lb < b.lb or (a.lb == b.lb and a.r < b.r)
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    if a[i] > n:
        a[i] = -1
l1 = []
z = int(n ** 0.5)
for i in range(m):
    (x, y) = map(int, input().split())
    l1.append(query(x, y, i))
l1.sort()
d = [0] * (n + 2)
l = 1
r = 0
ans = 0
fans = [0] * m
for i in l1:
    while r < i.r:
        r += 1
        if d[a[r - 1]] == a[r - 1]:
            ans -= 1
        d[a[r - 1]] += 1
        if d[a[r - 1]] == a[r - 1]:
            ans += 1
    while l > i.l:
        l -= 1
        if d[a[l - 1]] == a[l - 1]:
            ans -= 1
        d[a[l - 1]] += 1
        if d[a[l - 1]] == a[l - 1]:
            ans += 1
    while l < i.l:
        if d[a[l - 1]] == a[l - 1]:
            ans -= 1
        d[a[l - 1]] -= 1
        if d[a[l - 1]] == a[l - 1]:
            ans += 1
        l += 1
    while r > i.r:
        if d[a[r - 1]] == a[r - 1]:
            ans -= 1
        d[a[r - 1]] -= 1
        if d[a[r - 1]] == a[r - 1]:
            ans += 1
        r -= 1
    fans[i.ind] = ans
for i in fans:
    print(i)

Solution (Python):
import bisect
import collections
import heapq
import math

def do():
    (n, n_query) = map(int, input().split(' '))
    N = max(n, n_query) + 1
    nums = [0] * N
    count = [0] * N
    tmp = [int(c) for c in input().split(' ')]
    for (i, d) in enumerate(tmp):
        nums[i + 1] = d
        if d <= n:
            count[d] += 1
    l = [0] * N
    r = [0] * N
    s = [0] * N
    res = [0] * N
    for i in range(1, n_query + 1):
        (l[i], r[i]) = map(int, input().split(' '))
    for i in range(1, n + 1):
        if i <= count[i]:
            for j in range(1, n + 1):
                s[j] = s[j - 1] + (nums[j] == i)
            for j in range(1, n_query + 1):
                if s[r[j]] - s[l[j] - 1] == i:
                    res[j] += 1
    for i in range(1, n_query + 1):
        print(res[i])
do()

Solution (Python):
import collections

def do():
    (n, n_query) = map(int, input().split(' '))
    N = max(n, n_query) + 1
    nums = [0] * N
    count = collections.defaultdict(int)
    tmp = [int(c) for c in input().split(' ')]
    for (i, num) in enumerate(tmp):
        nums[i + 1] = num
        if num <= n:
            count[num] += 1
    l = [0] * N
    r = [0] * N
    s = [0] * N
    res = [0] * N
    for i in range(1, n_query + 1):
        (l[i], r[i]) = map(int, input().split(' '))
    for num in set(nums):
        if num <= count[num]:
            for i in range(1, n + 1):
                s[i] = s[i - 1] + (nums[i] == num)
            for j in range(1, n_query + 1):
                if s[r[j]] - s[l[j] - 1] == num:
                    res[j] += 1
    for i in range(1, n_query + 1):
        print(res[i] - 1)
do()