MNYC '17: Bells

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

There are N (1 \le N \le 100\,000) bells arranged in a line, labelled 1 to N. The i^\text{th} bell has a frequency of f_i Hz (1 \le f_i \le 10^8). There are Q (1 \le Q \le 50\,000) operations to perform.

There are two types of operations:

  • 1 i f Replace the i^\text{th} bell with one with a frequency of f Hz.
  • 2 l r Output the number of distinct frequencies between the l^\text{th} and r^\text{th} bell (inclusive).

There will be at most 1000 distinct frequencies at a time.

Fast input may be required.


For 10% of the points, 1 \le N, Q \le 100.

For 90% of the points, 1 \le N \le 100\,000, 1 \le Q \le 50\,000.

Input Specification

The first line contains two space separated integers, N Q, respectively the number of bells and the number of queries.

The next line contains N space separated integers, the frequency of the bells.

The next Q lines each contain a query in the format described above.

Output Specification

Output a single integer on its own line for each type 2 query.

Sample Input

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

Sample Output


Explanation for Sample Output

In the beginning, there are only 3 distinct frequencies which the bells have, 1 Hz, 2 Hz, and 4 Hz. After switching the second bell with one with a frequency of 1 Hz. There is only one distinct frequency among the first 3 bells.


  • 0
    Daniel123  commented on Jan. 7, 2017, 3:18 p.m.

    Submissions have been redjudged. New test cases were added.

    I apologize for the inconvenience.

  • 1
    jihua5758  commented on Jan. 7, 2017, 2:02 p.m.

    No bells are labeled 0 and there is no 0th bell, but some inputs have 0 as the bell number. I realized this because it keeps giving me "index out of bound" error. For the operations, I added if(index==0){index=1;} and it worked.

    • 0
      Daniel123  commented on Jan. 7, 2017, 2:18 p.m. edited

      Thank you for pointing this out. Will be fixed soon.

      EDIT: Issue has been fixed