DMPG '18 S5 - Mimi and Division

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 2.5s
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 Al,Al+1,,Ar which are divisible by x.
  2. 2 u v: Replace the uth 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:

1liriN

1uiN

1vi,xi200000

Subtask 1 [20%]

1N,Q2000

Subtask 2 [80%]

1N,Q200000

Input Specification

The first line will contain N and Q.
The next line will contain N space separated integers, A1,A2,,AN.
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

Copy
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

Copy
5
2
1
2

Comments


  • 2
    Jinx  commented on Nov. 30, 2021, 1:55 a.m.

    greatest birthday present of all time tbh


  • 7
    m2a  commented on May 18, 2021, 5:27 p.m.

    I too, also want an array as my birthday present.


  • -23
    DarthVader336  commented on May 24, 2018, 1:08 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 28
      quantum  commented on May 25, 2018, 4:57 a.m.

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


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

    Will an editorial be opened for this question?