We Are Discuss About CODECHEF SOLUTION
Increasing Addition Codechef Solution
Increasing Addition Codechef Solution
Problem
You have an array A of length N. In one operation, you can do the following:
- Select any subarray A_{L \ldots R} (1 \le L \le R \le N) and then add i to the i-th element of this subarray. Formally, we set A_j := A_j + (j – L + 1) for all L \le j \le R.
For example: if A = [2, 1, 5, 2] and we apply operation on A_{2 \ldots 4} then A becomes [2, 1 + 1, 5 + 2, 2 + 3] = [2, 2, 7, 5].
The minimum number of such operations required to sort A in non-decreasing order is termed as the goodness of A.
We want to process Q updates on A of the following form:
- \texttt{i x} : Set A_i := x where (1 \le i \le N).
Determine the goodness of A after each update.
Input Format
- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and Q — the size of the array A and the number of updates.
- The second line of each test case contains N space-separated integers A_1, A_2, \dots, A_N denoting the array A.
- The next Q lines each contain two integers i and x denoting the parameters of the update.
Output Format
For each test case, output Q integers, the goodness of the array after each update.
Constraints
- 1 \leq T \leq 10^4
- 2 \leq N \leq 10^5
- 1 \le Q \le N
- 1 \le A_i \le 10^9
- 1 \le x \le 10^9
- Sum of N over all test cases does not exceed 2 \cdot 10^5.
Subtasks
- Subtask 1 (50 points): 1 \le Q \le \min(5, N)
- Subtask 2 (50 points): Original constraints.
Sample 1:
Input
Output
2 3 2 3 2 1 3 10 2 1 4 2 2 2 2 2 4 2 4 1
1 2 0 1
Explanation:
Test Case 1: Initially A = [3, 2, 1].
- After first update: A = [3, 2, 10].
- Now we can apply the operation on A_{1 \ldots 2}. Then A becomes [4, 4, 10]. Therefore the goodness of A is 1.
- After second update: A = [3, 1, 10].
- Now we can apply the operation on A_{2 \ldots 2}. A becomes [3, 2, 10]. Now again we can apply the operation A_{2 \ldots 2}. A becomes [3, 3, 10]. Therefore the goodness of A is 2.
Test Case 2: Initially A = [2, 2, 2, 2].
- After first update: A = [2, 2, 2, 2].
- A is already in sorted order. Therefore the goodness of A is 0.
- After second update: A = [2, 2, 2, 1].
- Now we can apply the operation on A_{3 \ldots 4}. A becomes [2, 2, 3, 3]. Therefore the goodness of A is 1.
More Info
SOLUTION
Increasing Addition Codechef Solution
Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here JOIN NOW