Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Back to Back

By msabeer · Limits 2s, 512 MB

You will be given an array $A$ of size $N$ and $Q$ queries.

The queries will be given in the following form:

  • $\text{\textbf{1 L R}}$: You have to print the maximum sub-array sum from $L^{th}$ index to $R^{th}$ index (inclusive) of the array. That means, you need to print $MAX(\sum_{k = i}^{j} A[k])$ where, $L\le i\le j \le R$. You can’t select empty sub-array.
  • $\text{\textbf{2 L R X}}$: You have to make $X$ left circular shift of the values in the range $[L, R]$. For this problem, a left circular shift means removing the first element from the sub-array and inserting it at the end of the sub-array after changing its sign. For example, one left circular shift of a sub-array $[1, 2, 3, 4, 5]$ will be $[2, 3, 4, 5, -1]$.

Input

The first line will contain an integer $T$, the number of test cases. Then, the first line of each test case will contain an integer $N$, the size of the array $A$ and the next line will contain the array. After that, there will be an integer $Q$, the number of queries followed by $Q$ queries as explained above.

Constraints:

  • $1 \le T \le 10^3$
  • $1 \le N \le 10^5$
  • $1 \le Q \le 10^5$
  • $1 \le L \le R \le N$
  • $0 \le X \le R - L + 1$
  • $ |A_i| \le 10^5$
  • The sum of $N$ will be $\le 10^5$ over all the test cases
  • The sum of $Q$ will be $\le 10^5$ over all the test cases

Output

For each test case, print “Case #Y:” (without quotes) in the first line where $Y$ is the case number. Then for each query type 1, print the answer in a new line.

Sample

InputOutput
2
5
10 4 8 7 9
3
2 1 5 2
2 5 5 1
1 1 5
5
11 6 3 10 6
3
2 1 3 1
1 1 3
1 3 4
Case #1:
24
Case #2:
9
10

    Discussion

    Statistics


    75% Solution Ratio

    BigBagEarliest, 2w ago

    solaimanopeFastest, 0.4s

    BigBagLightest, 10 MB

    mahdi.hasnatShortest, 5157B

    Submit

    Login to submit

    Editorial

    Finding subarray maximum is a very common problem. With value updates in specific positions, it can...

    Related Contests