Division Queries and Updates

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.5s
Memory limit: 256M

Author:
Problem types

You are given an array A of size N, with all elements initially equal to 0. Support the following operations:

\;\;\;\;Type 1: Given l and r, increment all A_i with l \le i \le r by 1.
\;\;\;\;Type 2: Given l and r, return the sum of all \Bigl\lfloor \dfrac{A_i}{i} \Bigr\rfloor for l \le i \le r.

Constraints

For all subtasks:

1 \le N \le 10^9

1 \le Q \le 2 \times 10^5

1 \le t_i \le 2

1 \le l_i \le r_i \le N

Subtask 1 [20%]

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

Subtask 2 [80%]

No further constraints.

Input Specification

The first line contains 2 integers N and Q, the size of the array and the number of operations to be performed.

The next Q lines each contain 3 integers t_i \; l_i \; r_i (1 \le i \le Q), the type number of the i^{th} operation and the parameters l and r for that operation.

Output Specification

For each operation of type 2 output an integer on its own line, the return value of the operation.

Sample Input

8 8
2 1 8
1 1 4
2 1 2
2 2 8
1 2 3
1 2 7
1 2 8
2 1 8

Sample Output

0
1
0
4

Explanation

Right before the last operation, A = [1, 4, 4, 3, 2, 2, 2, 1]. The sum of all \Bigl\lfloor \dfrac{A_i}{i} \Bigr\rfloor for 1 \le i \le 8 is 1 + 2 + 1 + 0 + 0 + 0 + 0 + 0 = 4.


Comments

There are no comments at the moment.