P4497 [WC2011] Point-Picking Game

Xiao W and Xiao Y both enjoy a “point-picking game.” In the game, each of the two players produces a number as their “score” through some operation, and the player with the larger score wins. The rules of the “point-picking game” are as follows: 1. At the start of the game, you are given a positive integer sequence with $n$ elements, $U=(u_1, u_2, \cdots, u_n)$. 2. An index sequence $I=(i_1, i_2, \cdots, i_m)$ of $U$ is an integer sequence satisfying $1 \leq i_1 < i_2 < \cdots < i_m \leq n$ (where $m$ can be $0$, i.e., the sequence can be empty), and its corresponding subsequence of $U$ is $V=(u_{i_1}, u_{i_2}, \cdots, u_{i_m})$. 3. The score $D(I)$ corresponding to the index sequence $I=(i_1, i_2, \cdots, i_m)$ is defined as $D(I)=\sum_{p=1}^m u_{i_p} \times (-1)^p$. 4. During the game, the two players each choose an index sequence, and the one whose chosen index sequence corresponds to a larger score $D(I)$ wins. However, in every game, Xiao W can always compute, accurately and flawlessly, the optimal index sequence that maximizes the score. To make the game more competitive, they added the following extra rules: Ex1. Xiao W may choose a non-empty interval $[l, r]$ and increase $u_l, u_{l+1}, \cdots, u_r$ by an integer $c$ simultaneously; the new sequence replaces the original sequence $U$. Ex2. When they play a “point-picking game” on the current sequence $U$, Xiao Y is allowed, after Xiao W has chosen the optimal index sequence $I_W=(i_1, i_2, \cdots, i_m)$, to modify $I_W$ any number of times. Each modification follows the rules below: (1) Arbitrarily choose a positive integer $k$ satisfying $2k+1 \leq m$, and two non-negative integers $z_1, z_2$ satisfying $i_{2k} + z_1 < i_{2k+1} - z_2$; (2) Change $i_{2k}$ to $i_{2k} + z_1$, and change $i_{2k+1}$ to $i_{2k+1} - z_2$. If, after some number of modifications by Xiao Y to the index sequence $I_W$ chosen by Xiao W, the corresponding score is less than or equal to $0$, then Xiao Y wins. Now, given the information about Xiao W’s Ex1 operations, for each “point-picking game,” please help them compute: a) What is the score of the optimal index sequence that Xiao W can initially choose? b) What is the minimum number of modification operations Xiao Y needs in order to win, i.e., to make $D(I_W) \leq 0$?

The first line of the input file joy.in contains a positive integer $T$, the number of groups of testdata. Then follow $T$ groups of data. For each group of data, the first line contains two integers $n$ and $q$, denoting the number of elements in $U$ and the number of events, respectively. The next line contains $n$ positive integers separated by single spaces, where the $i$-th integer is the $i$-th element $u_i$ in the initial sequence. The following $q$ lines each describe an event (given in chronological order). The first number in each line is either $0$ or $1$, indicating the type of the event. If it is $0$: after the $0$ there are three integers $l$, $r$, and $c$ (all separated by single spaces), meaning Xiao W increases $u_l, u_{l+1}, \cdots, u_r$ by $c$. If it is $1$: the two players play a “point-picking game,” and you need to output the corresponding result. The input guarantees that all elements in the sequence $U$ are always positive integers.

The output file is joy.out. For each group of testdata, for each “point-picking game” in order, output one line containing two integers separated by a single space, $D_{max}$ and $X$, where - $D_{max}$ is the score of the optimal index sequence that Xiao W can choose for the current sequence $U$; - $X$ is the minimum number of modification operations that Xiao Y needs to win. If Xiao Y cannot win no matter how many operations are performed, output ```-1```. The data guarantee that the optimal index sequence is always unique.

Scoring rules: - A test point contains multiple groups of testdata. For that test point: - If all $D_{max}$ are correct but some $X$ is incorrect, you get 3 points. - If all $X$ are correct but some $D_{max}$ is incorrect, you get 7 points. - If all answers are correct, you get 10 points. Sample explanation: - The input contains two groups of testdata. - In the first group: In the first “point-picking game,” the optimal index sequence is $(1, 2, 4, 5)$. Xiao Y needs only one modification: choose $k=1$ and non-negative integers $z_1=1$, $z_2=0$. After the modification, the index sequence becomes $(1, 3, 4, 5)$, and Xiao Y wins. - In the third “point-picking game,” the sequence $U$ is $(9, 8, 6, 5, 3)$. Xiao W chooses the empty sequence as the optimal index sequence, yielding a score of $0$. In this case, Xiao Y cannot make any modification (nor is any modification needed), and Xiao Y already wins. Constraints: - For 10% of the data, $n, q \leq 13$. - For 30% of the data, $n, q \leq 1000$. - For another 20% of the data, $T=1$ and $n \leq 40000$. - For 100% of the data, $T \leq 3$ and $n, q \leq 10^5$, and the initial sequence $U$ satisfies $0 < u_i < 2^{31}$ and $|c| < 10^5$. Translated by ChatGPT 5