这道题的题意是给你一串数字,再给你一对序号,满足1出现一次,2出现两次,3出现三次以此类推,找出某对序号中有多少数字满足以上规律。莫队算法,树状数组,前缀和都可以解决这个问题,代码量最少的自然是前缀和,但是莫队算法的时间复杂度要小于前缀和很多。
D. Little Elephant and Array
time limit per test4 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
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.
Examples
inputCopy
7 2
3 1 2 2 3 3 7
1 7
3 4
outputCopy
3
1
分析:
许多方法可以做这道区间查询的题目
该题目可归纳为:(有一区间满足数字的个数==数字本身,求有多少组这样的数字)
因为是区间查询,而利用前缀和可以求得任意