TTC '18 Contest 1 P5 - Cancer

View as PDF

Submit solution

Points: 12
Time limit: 3.0s
Memory limit: 512M

Author:
Problem types

You are given an array a of length N, and Q queries, of the following forms:

  • 1 l r Output the number of cancer integers in the subarray [l, r] (1 \le l \le r \le N).
  • 2 i v Change the element at position i to be of value v (1 \le i \le N, 1 \le v \le 10^9).

We define a cancer integer as an integer with exactly 3 divisors.

Input Specification

The first line will contain two integers, N, Q (1 \le N,Q \le 10^5).

The second line will contain N space-separated integers a_1, a_2, a_3, \ldots, a_N (1 \le a_i \le 10^9), the initial array.

The next Q lines will each contain a valid query as defined above.

Output Specifcation

For each type 1 query, output the number of cancer integers in the subarray [l, r], on its own line.

Sample Input

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

Sample Output

1
0
1

Comments

There are no comments at the moment.