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.