Editorial for DMPG '18 S5 - Mimi and Division

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

For $20\%$ ~20\%~ of points, it suffices to iterate through all elements in the range $[l, r]$ ~[l, r]~ and check if they are divisible by $x$ ~x~ in $\mathcal O(N)$ ~\mathcal O(N)~ and update a number in $\mathcal O(1)$ ~\mathcal O(1)~.

Time Complexity: $\mathcal O(QN)$ ~\mathcal O(QN)~

For the remaining $80\%$ ~80\%~ of points, we can divide the array into $\mathcal O(\sqrt N)$ ~\mathcal O(\sqrt N)~ blocks of size $\mathcal O(\sqrt N)$ ~\mathcal O(\sqrt N)~. Maintain an array $A[1, 2, \dots, 200\,000]$ ~A[1, 2, \dots, 200\,000]~ for each block, where $A[i]$ ~A[i]~ is the number of elements in the corresponding block divisible by $i$ ~i~.

An update can be done in $\mathcal O(\sqrt x)$ ~\mathcal O(\sqrt x)~ time, as there are no more than $2\sqrt x$ ~2\sqrt x~ factors of any positive integer $x$ ~x~.

A query can be done in $\mathcal O(\sqrt N)$ ~\mathcal O(\sqrt N)~ time: a query will iterate over no more than $2\sqrt N$ ~2\sqrt N~ individual elements and $\sqrt N$ ~\sqrt N~ blocks. The individual elements can be checked using the modulo operator, and the blocks can be queried using the lookup table $A$ ~A~.

Time Complexity: $\mathcal O(N \sqrt A + Q \sqrt N + Q \sqrt A)$ , where $A$ ~A~ is the maximum value of any element in the array.

Comments

-18

DarthVader336 commented on May 24, 2018, 3:59 a.m.

What is x?

How do you split the array into sqrt(N) blocks when sqrt(N) is not an integer.

Can you give a simple example with the method for the second subtask?

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

34

Plasmatic commented on Feb. 3, 2019, 5:17 a.m.

$\sqrt{no} \sqrt{u}$ ~\sqrt{no} \sqrt{u}~