Interactive Tree Cutting and Magic Operation

You are given an array of N non-negative integers \(h_1, h_2, \cdots, h_N\). You have to process \(Q\) operations on this array. There are three types of operations:

• Operation 1 (Cut): Given integers \(l, r, k\), perform the following operation exactly \(k\) times:
  • If \(\max_{i \in [l, r]} \{h_i\} = 0\) then do nothing.
  • Otherwise, find \(x = \min\{ i \in [l, r] : h_i = \max_{j \in [l, r]} \{h_j\} \}\) and update \(h_x \gets h_x - 1\).
  In mathematical notation: \[ \text{If } \max_{i \in [l, r]} \{h_i\}=0, \text{ do nothing. Otherwise, let } x=\min\arg\max_{i\in[l,r]}\{h_i\} \text{ and set } h_x\gets h_x-1. \]
• Operation 2 (Magic): Given integers \(x, v\), set \(h_x \gets v\).
• Operation 3 (Inspect): Given integers \(l, r\), output the sum \(\sum_{i=l}^{r} h_i\).

Implementation Details:

You need to implement the following functions. You should not implement the main function. Our sample grader will call these functions.

// C++ prototype style
void initialise(int N, int Q, int h[]);
void cut(int l, int r, int k);
void magic(int i, int x);
long long int inspect(int l, int r);

Function Descriptions:

• initialise: Called exactly once at the beginning. Parameters:
  • N: Size of the array.
  • Q: Number of operations.
  • h[]: An array of length \(N+1\) (indexed from 1) representing the initial values \(h_1, h_2, \ldots, h_N\).
• cut(l, r, k): Performs Operation 1 as described.
• magic(i, x): Performs Operation 2 as described.
• inspect(l, r): Performs Operation 3 and returns the computed sum.

inputFormat

The input for the sample grader is structured as follows:

1. The first line contains two integers \(N\) and \(Q\): the number of elements in the array and the number of operations.
2. The second line contains \(N\) non-negative integers: \(h_1, h_2, \ldots, h_N\).
3. The next \(Q\) lines describe an operation. Each operation is one of the following formats:
   • For a cut operation: 1 l r k
   • For a magic operation: 2 x v
   • For an inspect operation: 3 l r (this operation produces an output)

outputFormat

For each inspect operation (Operation 3), output the sum \(\sum_{i=l}^{r} h_i\) on a separate line.

sample

5 4
2 3 1 0 4
1 1 3 2
3 1 3
2 5 1
3 1 5

4
5