Tom and Jerry | Practice Problems

Tom and Jerry

★★★★★

4.3

3 votes

Advanced Data Structures, Data Structures, Lazy Propagation in Interval/Segment Trees

Details

Submissions

Discussion

Editorial

Problem

Tom and Jerry are everyone's favorite. Jerry who loves cheese the most, was given a track of $N$ steps. Each step of the track contains a piece of cheese which has a happiness level of $A_i$ for $i^{th}$ step. Tom wants to test Jerry's intelligence and love for the cheese. To test Jerry, Tom will change his track and will ask him where he would like to start. If Jerry starts with step x then he can't go at steps less than x, more formally he would have to move in the forward direction only, additionally, he can't jump/skip a step i.e. he needs to move continuously. He can leave the track whenever he wants. Jerry wants to be happy as much as he can be by eating the pieces of cheese. Tom will change the track by replacing the pieces of cheese with new ones.

You will be asked $3$ types of queries as follows:

$1\space L\space R\space X$ $-$ Tom changes the track from $L$ to $R$ by replacing the piece of cheese with a new piece with happiness equal to $X$ . (formally $A_i = X$ for all $L \le i \le R$ )

$2 \space L\space R$ $-$ Jerry needs to answer the maximum happiness he can achieve by selecting any starting point in the track. More formally, if he starts at step $i$ and leaves the track at step $j$ then the answer is the sum of all happiness of cheese i.e. $\sum_{k = i}^{j} A_k$ . Jerry would try to maximize the happiness that he may get. (where $L \le i \le j \le R$ )

Note: Jerry may have negative happiness too. (i.e. he should eat at least one cheese).

Input format:

The first line of input contains an integer $T$ (the number of test cases).
The first line of each test case contains an integer $N$ (the number of steps at the track).
The second line contains $N$ integers $A_1, \space A_2 \space, A_3, ..... \space A_N$ (where the $i^{th}$ element denotes the happiness of the cheese placed on the $i^{th}$ step of the track.
The third line contains an integer $Q$ (the number of queries).
Next $Q$ lines contain space-separated integers either $1\space L \space R \space X$ or $2 \space L \space R$ denoting the query asked by Tom.
Additionally, it's guaranteed that there will be at least one query of type $2$ .

Output format:

For each test case, for each query of type $2$ , print a single integer denoting the answer to that query.

Constraints:

$1 \le T \le 10 \\ 1 \le N, Q \le 2 * 10^5 \\ -10^9 \le A_i, X\le 10^9 \\ 1 \le L \le R \le N$

Time Limit: 5

Memory Limit: 256

Source Limit:

Explanation

Initially, the track was $[1, 2, 3, 4, 5, 6, 7]$ .

Now, Tom changes the track by placing the cheeses having happiness $-2$ from step $4$ to $5$ . So the track became $[1, 2, 3, -2, -2,6, 7]$ .

Now, Tom asks Jerry to choose any start and end point between steps $1$ and $6$ so Jerry moves as $[\underline{1, 2, 3, -2, -2,6}, 7]$ , so Jerry may get the happiness of $8$ .

Now, Tom asks Jerry to choose any start and end point between steps $3$ and $7$ so Jerry moves as $[1, 2, 3, -2, -2,\underline{6, 7}]$ , so Jerry may get the happiness of $13$ .

Now, Tom changes the track by placing the cheeses having happiness $1$ from step $3$ and $4$ . So the track became $[1, 2, 1, 1, -2,6, 7]$ .

Now, Tom asks Jerry to choose any start and end point between steps $3$ and $6$ so Jerry moves as $[1, 2, \underline{1, 1, -2,6}, 7]$ , so Jerry may get the happiness of $6$ .