Problem

Jay likes sequences, so he use to playing with a sequence of size N. He will transform the sequence according to K queries, and the format and process of the queries are as follows:

• L R X: Let’s say the sequence sorted in ascending order is A[1], A[2], …, A[N].
• First, add X to A[L], A[L+1], …, A[R].
• Then, sort the sequence again in ascending order.

Print the sequence after performing all the queries in order.

Input

tip The first line is given with N and K separated by a space. (1 ≤ N ≤ 100000, 1 ≤ K ≤ 1000)
The second line is given with N integers that make up the sequence, each having an absolute value of less than or equal to 10^18.
From the third line to the (K+2)th line, the queries L R X are given. (1 ≤ L ≤ R ≤ N, |X| ≤ 10^9)

Output

tip Print the sequence after performing all the queries in order.

Example: (tip)

\(Input:  
7 3  
1 2 3 4 5 6 7  
1 6 3  
2 7 -4  
4 5 6  

Output: 
1 2 3 4 5 9 10\)

How to Approach?

Though there is no single correct solution, there are effective ones. I usally take follow steps:

1. we need a input function
2. validation function to prove user input proper or not
3. print function to print out our output
4. do function (This can be further divided into several actions)
5. (if we need)calculate function

step1. Input function

First we need input function. In java, there exist some other input method but I usually use this method:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public static void getUserInput(ArrayList<Long> sequence, int[] nk) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        nk[0] = Integer.parseInt(st.nextToken()); // N
        nk[1] = Integer.parseInt(st.nextToken()); // K
        
        st = new StringTokenizer(br.readLine()); // Tokenizing the sequence line
        while (st.hasMoreTokens()) {
            sequence.add(Long.parseLong(st.nextToken()));
        }
    }

By using BufferedReader, you can quickly get input values.

step2. validation function

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

n, k = map(int, input().split())
sequence = list(map(int, input().split()))

while(k > 0):
    l, r, x = map(int, input().split())
    for i in range(l, r+1):
        sequence[i] += x
    sequence.sort()
    k -= 1

print(*sequence)