Home => ProblemSet => 3.2-63:次数统计
Problem2064--3.2-63:次数统计

2064: 3.2-63:次数统计

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

给定一个大小为N的数组，数组中所有元素的大小<=N。
需要回答M个查询，每个查询的形式是L，R。需要回答在范围[ L，R ]中至少重复3次的数字的个数。

Input

第一行两个正整数n m;
第二行n个正整数，空格分隔；
接下来m行，每行两个数L R；

Output

m行，每行一个数字表示L R中出现3次及以上的元素数目

Sample Input Copy 

10 2
1 2 3 1 1 2 1 2 3 1
1 5
2 9

Sample Output Copy 

1
2

HINT

1 <= N, M <= 100000
1 <= 数组元素 <= N

Source/Category

莫队 数据结构 线段树 树状数组 
[ Submit ] [ Status ]