Масив і часткові суми#225
Масивом префіксних сум масиву цілих чисел довжини називається такий масив довжини , що b_i = a_1+a_2+\ldots+a_i.
Масивом суфіксних сум масиву цілих чисел довжини називається такий масив довжини , що b_i = a_n+a_{n-1}+\ldots+a_i.
Назвемо нормалізацією масиву цілих чисел довжини виконання операції присвоєння a_i \leftarrow \max(\min(a_i, 10^{18}),-10^{18}) для 1 \le i \le n.
Задано масив цілих чисел довжини .
Дозволяється виконувати операції трьох типів:
замінити кожен елемент масиву на протилежний (виконати операцію присвоєння a_i \leftarrow (-a_i) для 1 \le i \le n);
вибрати довільний підвідрізок масиву та замінити його на масив його префіксних сум, після чого нормалізувати масив ;
вибрати довільний підвідрізок масиву та замінити його на масив його суфіксних сум, після чого нормалізувати масив .
Знайдіть найкоротшу послідовність операцій, необхідних для того, щоб усі елементи масиву стали невід'ємними.
Зверніть увагу, що для деяких блоків тестів дозволяється знайти послідовність операцій, що не є найкоротшою з можливих.
У першому рядку задано два цілі числа , (1 \le n \le 2 \cdot 10^5, 0 \le g \le 8) — довжина масиву та номер блоку тестів відповідно.
У другому рядку задано цілих чисел a_1,a_2,\ldots,a_n (-1 \le a_i \le 1) — елементи масиву.
У першому рядку виведіть одне ціле число — мінімальну кількість операцій, необхідних для того, щоб усі елементи масиву стали невід'ємними.
У наступних рядках виведіть опис операцій. Описи операцій першого типу виводіть у форматі «1». Описи операцій другого та третього типів виводіть у форматах «2 l r» та «3 l r» відповідно, де та (1 \le l \le r \le n) позначають ліву та праву межі підвідрізка чергової операції.
Якщо існує кілька правильних відповідей, дозволяється вивести будь-яку з них.
Приклад 1
У першому прикладі масив змінюється двічі:
після виконання операції третього типу з параметрами l=1, r=3 масив стає рівним [1,1,1,-1,-1,-1,1];
після виконання операції другого типу з параметрами l=1, r=7 масив стає рівним [1,2,3,2,1,0,1].
Нехай для певного тесту мінімальна кількість операцій, необхідних для того, щоб усі елементи масиву стали невід'ємними, рівна m_{ans}, а ваше рішення використовує m_{user} операцій.
( балів): m_{ans} \le 1;
( балів): ваш розв'язок вважатиметься правильним, якщо m_{user} \le 100. Можна довести, що завжди існує послідовність не більше ніж з операцій при заданих обмеженнях;
( балів): ваш розв'язок вважатиметься правильним, якщо m_{user} \le m_{ans} + 3;
( балів): ваш розв'язок вважатиметься правильним, якщо m_{user} \le m_{ans} + 1;
( балів): n \le 3000; гарантується, що усі найкоротші послідовності операцій містять лише операції другого типу;
( балів): гарантується, що усі найкоротші послідовності операцій містять лише операції другого типу;
( балів): n \le 3000;
( бал): без додаткових обмежень.