18435번 - Fire 서브태스크다국어

There are N districts in JOI Village, numbered from 1 to N. These districts are located in a line. Now, a fire occurs in each district. At time 0, the strength of the fire in the i-th district (1 ≤ i ≤ N) is S_i (S_i > 0).

At time 0, the wind blows from the 1st district to the N-th district. For every pair of neighboring districts, if the fire in the upwind district is stronger than the fire in the downwind district at time t (0 ≤ t), the strength of the fire in the downwind district at time t +1 will be the strength of the fire in the upwind district at time t. Otherwise, the strength of the fire in the downwind district at time t +1 and time t are the same. Namely, if the strength of the fire in the i-th district (1 ≤ i ≤ N) at time t (0 ≤ t) is denoted by S_i(t), we have S_i(t) = max{S_i−1(t − 1), S_i(t − 1)} for every t (1 ≤ t). Here, for any t (0 ≤ t), we put S₀(t) = 0. For any i (1 ≤ i ≤ N), we put S_i(0) = S_i.

You are a firefighter. You have Q plans to extinguish the fire. You are planning to do only one of the Q plans. In the j-th plan (1 ≤ j ≤ Q), you will use fire extinguishing agent for the k-th district for every k with L_j ≤ k ≤ R_j, and extinguish the fire in these districts. If the strength of the fire in a district is s, you need s liters of fire extinguishing agent to extinguish the fire in that district. Therefore, the amount of fire extinguishing agent needed for the j-th plan is S_Lj(T_j) + S_Lj+1(T_j) + · · · + S_Rj (T_j) liters. In order to examine the plan to be done, you want to know the amount of fire extinguishing agent needed for each plan.

Write a program which, given the strength of the fire at time 0 and information of fire extinguishing plans, calculates the amount of fire extinguishing agent needed for each plan.

Read the following data from the standard input. Given values are all integers.

N Q
S1 . . . SN
T1 L1 R1
.
.
.
TQ LQ RQ

Write Q lines to the standard output. In the j-th line (1 ≤ j ≤ Q), output the amount of fire extinguishing agent needed for the j-th plan.

• 1 ≤ N ≤ 200 000.
• 1 ≤ Q ≤ 200 000.
• 1 ≤ S_i ≤ 1 000 000 000 (1 ≤ i ≤ N).
• 1 ≤ T_j ≤ N (1 ≤ j ≤ Q).
• 1 ≤ L_j ≤ R_j ≤ N (1 ≤ j ≤ Q).