UTS Open '21 P5 - State Taxes

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 2.0s
Java 4.0s
Memory limit: 256M

Author:
Problem type

In the land of UTS, the government has started to automate the taxes of their citizens. To function properly, this automated system needs to know the total revenue of every citizen by the end of the year. As such, the government has hired you to figure this out for them!

At the start of the year, the N citizens of UTS numbered from 1 to N each start out with a specific salary a_i. A poorly conducted citizen could even have a negative salary! During the year, there are Q operations of salary changes or payments. On each salary change, all the citizens numbered from l_i to r_i have their salaries increased by x_i. On each payment, all the citizens numbered from l_i to r_i receive their salaries as revenue.

Please help the government find the total revenue of each citizen by the end of the year.

Constraints

For this problem, you MUST pass the sample case in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

1 \le N, Q \le 5 \times 10^5

1 \le l_i \le r_i \le N

-10^8 \le a_i, x_i \le 10^8

Subtask 1 [10%]

1 \le N, Q \le 10^3

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line of input contains 2 integers N and Q, the number of citizens and the number of operations.

The next line of input contains N integers a_i (1 \le i \le N), the initial salary of each citizen.

The next Q lines will be either of the following two forms:

  1. 1 l_i r_i x_i indicating that the salaries of the citizens numbered from l_i to r_i increased by x_i.

  2. 2 l_i r_i indicating that the citizens numbered from l_i to r_i received their salaries as revenue.

Output Specification

Output N space separated integers, with the i^\text{th} integer being the total revenue of the i^\text{th} citizen by the end of the year.

Sample Input

5 5
1 -3 7 4 2
1 2 3 -2
2 3 4
1 1 5 3
2 3 5
2 1 5

Sample Output

4 -2 21 18 10

Explanation

Initially, the list of salaries is [1, -3, 7, 4, 2] and the list of revenues is [0, 0, 0, 0, 0].

In the first operation, the citizens in the range [2, 3] have their salaries reduced by 2. The list of salaries is now [1, -5, 5, 4, 2].

In the second operation, the citizens in the range [3, 4] receive their salaries as revenue. The list of revenues is now [0, 0, 5, 4, 0].

In the third operation, the citizens in the range [1, 5] have their salaries increased by 3. The list of salaries is now [4, -2, 8, 7, 5].

In the fourth operation, the citizens in the range [3, 5] receive their salaries as revenue. The list of revenues is now [0, 0, 13, 11, 5].

In the fifth operation, the citizens in the range [1, 5] receive their salaries as revenue. The list of revenues is now [4, -2, 21, 18, 10].

At the end of the year, the list of revenues is [4, -2, 21, 18, 10], which is our desired result.


Comments

There are no comments at the moment.