An Array Problem

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Given an array a of length N, support Q of the following operations:

  • 1 l r v k Subtract v from all elements i\ (l \le i \le r) only if a_i > k.
  • 2 l r k Sum up all elements i\ (l \le i \le r) only if a_i > k.

1 \le l \le r \le N, 0 \le v \le 10^3, and 0 \le k \le 10^6.

Input Specification

The first line will contain two integers, N, Q\ (1 \le N, Q \le 10^3).

The next line will contain N integers, a_1, a_2, \ldots, a_N\ (0 \le a_i \le 10^6).

The next Q lines will each contain a valid operation as defined above.

Output Specification

For each type 2 operation, print out the desired answer on its own line.

Sample Input

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

Sample Output

1
4

Comments

There are no comments at the moment.