#2151. An Array and Partial Sums
An Array and Partial Sums
An Array and Partial Sums
题目描述
Problem . An Array and Partial Sums A prefix sum array of an integer array a of length n is an array b of length n such that bi = a1+a2+. . .+ai. A suffix sum array of an integer array a of length n is an array b of length n such that bi = an+an−1+. . .+ai. normalization a n We call the of an integer array of length performing the assignment ai ←max(min(ai, 1018), −1018) for 1 ≤i ≤n. An integer array a of length n is given. We are allowed to perform operations of three types:
- replace each element of array a with its opposite (perform the assignment ai ←(−ai) for 1 ≤i ≤n);
- select any subsegment of the array a and replace it with the array of its prefix sums, then normalize array a;
- select any subsegment of the array a and replace it with the array of its suffix sums, then normalize array a. Find the shortest sequence of operations required to make all elements of array a non-negative. Note that for some blocks of tests, it is allowed to find a sequence of operations that is not the shortest possible. Input The first line contains two integers n and g (1 ≤n ≤2 · 105, 0 ≤g ≤8) — the length of the array and the test group number, respectively. The second line contains n integers a1, a2, . . . , an (−1 ≤ai ≤1) — the elements of the array. Output In the first line, print a single integer m — the minimum number of operations required to make all elements of the array a non-negative. In the next m lines, output the descriptions of the operations. Output the descriptions of operations of the first type in the format “1”. Output the descriptions of operations of the second and third types in the formats “2 l r” and “3 l r”, respectively, where l and r (1 ≤l ≤r ≤n) denote the left and right boundaries of the subarray of the corresponding operation. If there are multiple correct answers, any of them may be printed. Note In the first example, the array a changes twice:
- after performing the third type of operation with parameters l = 1, r = 3, the array a becomes equal to [1, 1, 1, −1, −1, −1, 1];
- after performing the second type of operation with parameters l = 1, r = 7, the array a becomes equal to [1, 2, 3, 2, 1, 0, 1]. Examples test answer 7 0 2 0 0 1 -1 -1 -1 1 3 1 3 2 1 7 Page 1 of 2 Scoring Let the minimum number of operations required to make all elements of the array a non-negative for a certain test be mans, and your solution uses muser operations.
- (14 points): mans ≤1;
- (17 points): your solution will be considered correct if muser ≤100. It can be proved that there always exists a sequence of no more than 100 operations under the given constraints;
- (18 points): your solution will be considered correct if muser ≤mans + 3;
- (7 points): your solution will be considered correct if muser ≤mans + 1;
- (7 points): n ≤3000; it is guaranteed that all shortest sequences of operations contain only operations of the second type;
- (19 points): it is guaranteed that all shortest sequences of operations contain only operations of the second type;
- (17 points): n ≤3000;
- (1 point): no additional constraints. Page 2 of 2
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
7 0
0 0 1 -1 -1 -1 1
2
3 1 3
2 1 7