Gary and Queries
Tag(s):

Algorithms, Algorithms, Data Structures, Medium-Hard, Sqrt-Decomposition

Problem
Editorial
Analytics

Gary likes to solve algorithmic problems but he doesn't like problems that involve queries. His school teacher gave him an assignment full of problems but one of them involve queries. Can you help Gary in solving that problem so that he can go and play with his friends? The problem is :

Given an Array A consisting of N positive integers, you have to answer Q queries on it. Queries can be of the two types:

• $1\; X\; Y$ - Update the value of the Xth element in the array to Y.
• $2\; X$ - Print the value of $\sum_{i=1}^{n} \left \lfloor{\frac{A_i}{X}}\right \rfloor$ where $\left \lfloor{}\right \rfloor$ denotes Greatest Integer Function.

Input:
The first line contains two space separated integers N and Q.
Next line contains N space separated integers denoting array A.
Next Q lines contain queries of one of the above mentioned type format.

Output:
Answer to the each query of type 2 in a new line .

Constraints:
$1 \le N \le 5 * 10^5$
$1 \le Q \le 5 * 10^5$
$1 \le A_i, X, Y \le 5 * 10^5$

SAMPLE INPUT
5 4
3 3 4 1 2
1 3 2
2 5
1 4 4
2 1

SAMPLE OUTPUT
0
14

Explanation

After query 1 the array becomes : 3 3 2 1 2
Answer for query 2 is : $\left \lfloor{\frac{3}{5}}\right \rfloor + \left \lfloor{\frac{3}{5}}\right \rfloor + \left \lfloor{\frac{2}{5}}\right \rfloor + \left \lfloor{\frac{1}{5}}\right \rfloor + \left \lfloor{\frac{2}{5}}\right \rfloor = 0$
After query 3 the array becomes : 3 3 2 4 2
Answer for query 4 is : $\left \lfloor{\frac{3}{1}}\right \rfloor + \left \lfloor{\frac{3}{1}}\right \rfloor + \left \lfloor{\frac{2}{1}}\right \rfloor + \left \lfloor{\frac{4}{1}}\right \rfloor + \left \lfloor{\frac{2}{1}}\right \rfloor = 14$

Time Limit: 5,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor

Challenge Name

August Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Algorithms > Graphs
• Algorithms > Dynamic Programming
• Math > Combinatorics
• Algorithms > Graphs