Home => ProblemSet => 区间不同数之和
Problem2307--区间不同数之和

2307: 区间不同数之和

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

Description

有n个数a1, a2,...,an
有m个询问，每次给一个区间[l, r]，求区间里不同的数字之和，也就是说每一个数字出现次数只算一次

Input

第一行两个数n,m(1 <= n, m <= 2*105)
接下来一行n个数a1,a2,...,an(1 <= ai <= n)
接下来m行每行两个整数l, r(1 <= l <= r <= n)

Output

每行输出一个询问结果

Sample Input Copy 

5 5
2 2 3 2 1
1 5
2 3
2 4
1 2
3 5

Sample Output Copy 

6
5
5
2
6

Source/Category

数据结构 线段树 
[ Submit ] [ Status ]