The Power of 2
Sherlock Holmes has helped the London Police to solve a lot of cases and sent a lot of criminals to prison. But now he is getting bored as there is no interesting case to solve. So he decides to play a game with Watson to spend his time.
Initially he gives him an array of N numbers A1, A2, A3, … An. Now, he asks Watson to tell him the sum of the squares of all numbers in any subarray from Ai to Aj.
i.e. Ai2 + Ai+12 + ...+ Aj2.
To increase the difficulty of the task, he updates the numbers in any subarray from Ai to Aj from time to time. The update is performed in two steps-
1) He multiplies all numbers in the subarray by 2.
2) He divides all multiples of 2048 in the subarray by 2048.
Dr. Watson knows that if he is unable to answer Sherlock’s queries, Sherlock will boast about it for days. So he asks for your help to keep Sherlock’s ego under control.
The first line contains T, the number of test cases.
For each test case, the first line of input contains 2 integers N and Q(number of queries).
Next line contains N integer A1, A2, A3, … An.
Next Q lines contain each defines a query-
0 i j - Sherlock updates all the numbers in the subarray from Ai to Aj as defined above.
1 i j - Watson needs to tell the sum of squares of all numbers in the subarray from Ai to Aj.
For each query of the form 1 i j, output 1 line containing the answer to Sherlock's problem.
Input: 2 4 3 5 2 1 6 1 2 3 0 1 3 1 2 4 1 3 512 0 1 1 0 1 1 1 1 1 Output: 5 56 1
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions