Optimal Point Game with Modifications

In this problem, two players, W and Y, play a game called the "Point Game." Initially, a sequence ( U = (u_1,u_2,\dots,u_n) ) of positive integers is given. A non‐empty (or even empty) index subsequence ( I = (i_1,i_2,\dots,i_m) ) (with (1 \le i_1 < i_2 < \cdots < i_m \le n)) defines a subsequence ( V = (u_{i_1},u_{i_2},\dots,u_{i_m}) ) whose corresponding point value is defined by

[ D(I) = \sum_{p=1}^{m} u_{i_p} \times (-1)^p, ]

with the convention that (D(\emptyset)=0). In a normal game the player whose chosen subsequence yields a larger value of (D(I)) wins. It is known that player W can always compute an optimal subsequence ( I_W ) that maximizes (D(I)).

To make the contest more interesting, they add the following extra rules:

Ex1. Before each game, player W is allowed to choose a nonempty interval ([l,r]) and add an integer (c) (which may be negative, zero, or positive) to each (u_l,u_{l+1},\dots,u_r). The updated sequence replaces ( U ).

Ex2. After W picks his optimal index subsequence ( I_W=(i_1,i_2,\dots,i_m) ), player Y is allowed to apply the following modification operation arbitrarily many times. In each operation, he chooses a positive integer (k) satisfying (2k+1\le m) and two non‐negative integers (z_1,z_2) such that

[ i_{2k} + z_1 < i_{2k+1} - z_2. ]

Then, he modifies the subsequence by replacing ( i_{2k} ) with ( i_{2k}+z_1 ) and ( i_{2k+1} ) with ( i_{2k+1}-z_2 ). If after some modifications the point value corresponding to ( I_W ) becomes non–positive (i.e. (D(I_W) \le 0)), player Y wins.

Given the information for the Ex1 operations (each game involves exactly one interval update), your task is to help the players determine the following for each game:

(a) What is the maximum possible point value (D(I_W)) achievable by player W using an optimal even–length (or empty) index subsequence? (Recall that when an odd–length subsequence is chosen, its value is negative, so W will never choose that over the empty subsequence which gives 0.)

(b) Assuming W has chosen his optimal subsequence, what is the minimum number of modification operations required by player Y so that after his modifications the resulting (D(I_W)) becomes (\le 0)?

A key observation is that any even–length subsequence ( I = (i_1,i_2,\dots,i_{2k}) ) contributes

[ D(I) = (u_{i_2} - u_{i_1}) + (u_{i_4} - u_{i_3}) + \cdots + (u_{i_{2k}} - u_{i_{2k-1}}). ]

Thus, player W’s problem reduces to choosing disjoint index pairs ((i, j)) with (i < j) so that (u_j - u_i) is positive and the total sum is maximized. Furthermore, player Y can invalidate each pair with a single modification operation. Hence, if the optimal subsequence uses (P) pairs then Y needs at least (P) operations to force (D(I_W)\le 0).

It can be shown that the optimal total point value equals the maximum alternating sum obtainable by a dynamic programming approach with two states: one representing an even number of selections and one representing an odd number. We define the recurrence as follows:

Define two states:

• (dp_0): the maximum value obtainable using an even number of selections (initially (dp_0=0)).
• (dp_1): the maximum value obtainable using an odd number of selections (initially (dp_1=-\infty)).

For each element (u) in (U), update:

[ \begin{aligned} \text{new}{1} &= \max( dp_1,; dp_0 - u ) \[6pt] \text{new}{0} &= \max( dp_0,; dp_1 + u ) \end{aligned} ]

Also, maintain the count of pairs used when updating (dp_0) (each update from (dp_1+u) completes one pair) so that the minimum number of Y’s operations equals that count (or 0 if the optimal (dp_0=0)).

Your program should process multiple games. For each game, first perform the Ex1 update on (U) and then compute (a) the optimal (D(I_W)) and (b) the minimal number of operations needed by Y.

\textbf{Input Format:}

The first line contains two integers (n) and (Q), denoting the length of the sequence and the number of games respectively.\n\nThe second line contains (n) space–separated positive integers representing ( U ).\n\nEach of the following (Q) lines contains three integers (l), (r) and (c) representing an Ex1 update: add (c) to every (u_i) for (l \le i \le r).

\textbf{Output Format:}\n\nFor each game, output two integers on a single line: the first is the optimal point value (D(I_W)) computed by W, and the second is the minimum number of modification operations required by Y so that the resulting point value becomes (\le 0). If (D(I_W)=0) then Y does not need to make any moves, and you should output 0 for the second number.

inputFormat

The input begins with a line containing two integers \(n\) and \(Q\) (the number of elements and the number of games respectively). The next line contains \(n\) space–separated integers representing the initial sequence \(U\). Each of the following \(Q\) lines contains three integers \(l\), \(r\) and \(c\) indicating that for that game, every element \(u_l, u_{l+1}, \ldots, u_r\) is increased by \(c\).

Constraints:\n
\(1 \le n, Q \le 10^5\) (for example)\n
\(1 \le u_i \le 10^9\)\n
\(1 \le l \le r \le n\)\n
\( -10^9 \le c \le 10^9\)

outputFormat

For each game (update), output a single line with two space–separated integers. The first integer is the maximum point value \(D(I_W)\) that player W can obtain, and the second integer is the minimum number of modification operations needed by player Y to reduce \(D(I_W)\) to \(\le 0\). If the optimal value is 0, output 0 for the number of operations.

sample

3 2
1 5 10
1 2 -1
2 3 2

10 1
12 1

</p>