牛客网暑期ACM多校训练营(第一场) J Different Integers

  • 2018-07-23
  • 47
  • 0

题目:

Given a sequence of integers a_1, a_2, …, a_n and q pairs of integers (l_1, r_1), (l_2, r_2), …, (l_q, r_q), find count(l_1, r_1), count(l_2, r_2), …, count(l_q, r_q) where count(i, j) is the number of different integers among a_1, a_2, …, a_i, a_j, a_{j + 1}, …, a_n.

Input:

The input consists of several test cases and is terminated by end-of-file.
The first line of each test cases contains two integers n and q.
The second line contains n integers a_1, a_2, …, a_n.
The i-th of the following q lines contains two integers l_i and r_i.

Output:

For each test case, print q integers which denote the result.

Sample Input:

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

Sample Output:

2
1
3

题目链接

使用离线树状数组做法,先读入询问数据,之后按照右端点升序处理,最后输出结果。

在数列中从左至右遍历,当遍历到i位置时若a[i]的最后一次出现位置是i位置,因为询问是按照右端点升序处理,所以在处理下一次询问中只用根据first[a[i]]也就是a[i]第一次出现的位置和询问左端点的位置关系判断a[i]是否在1\rightarrow lr \rightarrow n之间,在遍历时不断维护树状数组count。

AC代码:

评论

还没有任何评论,你来说两句吧