Copy and Paste
All submissions for this problem are available.
In an exam in IIT Kanpur, the question paper consists of infinite questions. Ram, being a studious guy, aims to attempt infinite questions. In the i-th question, Ram answers are worth R[i] marks. However, he does not know the answer to all, and instead of thinking about the questions, repeats his answer after every S questions, i.e., the answer given by Ram for the K-th question is same as the answer for (K - S)-th question and so the marks obtained for question K and question K-S are also the same.
Shyam, on the other hand, hardly studies and has made up his mind to attempt atmost N questions. He plans to copy the answer to these questions from Ram. If Shyam wishes to write answers to all between question X and question Y, he wants to know the corresponding answers by Ram for all questions between M and M+Y-X, where M is a parameter decided by Shyam. For each answer copied, he would earn same marks as Ram earned for the corresponding answer. If at the end of the exam, Shyam has not attempted any of the N questions, he receives zero marks for that question.
Now while correcting Shyam's answer sheet, the teacher wishes to check answers for questions between A and B. She asks Ram as what would be the maximum marks he would obtain if she checks some continuous questions in between A and B.
Help Ram in answering these questions and passing the exam.
First Line contains 3 space separated integers S N T.
Next Line Contains S space separated integers, representing the marks worth of first S answers of Ram, i.e., i-th integer represents R[i].
T lines follows, containing T operations, one per line.
Each operation is either of the two forms
U X Y M - To copy Ram's answer from M to M+Y-X.
Q A B - To report the maximum marks that can be obtained on correcting continuous questions between A and B.
For each of the query operation (ones starting with Q), output a single integer in a line, the result of that query.
- 1 ≤ S ≤ 1000
- 1 ≤ N ≤ 10^5
- 1 ≤ M ≤ 10^9
- 1 ≤ T ≤ 10^5
- abs(R[i]) ≤ 1000
- 1 ≤ A,B,X,Y ≤ N
5 10 4
10 -6 -7 11 12
U 1 5 3
Q 2 4
U 2 9 3
Q 3 9
Initially scores of N questions:: 0 0 0 0 0 0 0 0 0 0
Marks After Update :: -7 11 12 10 -6 0 0 0 0 0
Result of Query(Maximum Sum Subarray from 2 to 4):: 33 (11+12+10)
Marks After Update:: -7 -7 11 12 10 -6 -7 11 12 0
Result of Query(Maximum Sum Subarray from 3 to 9):: 43 (11+12+10+(-6)+(-7)+11+12)
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 4.9.2, GO, JAVA|
Fetching successful submissions