DMPG '18 S5 - Mimi and Division

View as PDF

Submit solution



Points: 15 (partial)
Time limit: 5.0s
Memory limit: 512M
Author:

Problem type

For her birthday, Mimi is given an array A of N integers. She then proceeds to perform Q operations:

  1. 1 l r x: Count how many numbers there are in the subarray A_l, A_{l+1}, \ldots A_{r-1}, A_{r} which are divisible by x.
  2. 2 u v: Replace the u^{\text{th}} number with v.

Because you forgot to get Mimi a present, you decide to write a program to verify her answers.

Constraints

For all subtasks,
1 \le l_i \le r_i \le N
1 \le u_i \le N
1 \le v_i, x_i \le 200\,000

Subtask 1 [20%]

1 \le N, Q \le 2\,000

Subtask 2 [80%]

1 \le N, Q \le 200\,000

Input Specification

The first line will contain N and Q.
The next line will contain N space separated integers, A_1, A_2, \ldots A_{N-1}, A_N.
The next Q lines will each contain a valid query.

Output Specification

The answer to each query of type 1, each on a new line.

Sample Input

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

Sample Output

5
2
1
2

Comments


  • -9
    DarthVader336  commented on May 23, 2018, 9:08 p.m.

    Thanks for writing the editorial, though I don't think the editorial makes sense. Can the author please be clearer?


    • 9
      quantum  commented on May 25, 2018, 12:57 a.m.

      Editorials do not exist so that you can get free points.


  • 1
    DarthVader336  commented on May 13, 2018, 2:45 p.m.

    Will an editorial be opened for this question?