Покарає чи заб’є?
Обмеження: 2 сек., 256 МіБ
За минулий тиждень Тойлет-мен наловив дуже багато злочинців, тож тепер його завдання — покарати всіх цих негідників.
Усього злочинців є \(n\), і вони розміщені зліва направо та пронумеровані числами від 1 до \(n\) включно. У початковий момент часу в \(i\)-го злочинця рівень здоров’я є рівним \(h_i\). Коли Тойлет-мен карає якогось злочинця, рівень його здоров’я зменшується на одиницю. При цьому, якщо рівень перед покаранням є рівним 0, то він не змінюється, тобто здоров’я ніколи не стає від’ємним.
Тойлет-мен хоче обробити \(m\) запитів. Запити бувають трьох типів:
L
\(c\) — покарати перших \(c\) злочинців \((1 \le c \le n)\).R
\(c\) — покарати останніх \(c\) злочинців \((1 \le c \le n)\).Q
\(x\) — визначити, який поточний рівень здоров’я в \(x\)-го злочинця \((1 \le x \le n)\).
Допоможіть Тойлет-менові опрацювати всі його запити.
Вхідні дані
У першому рядку задано два цілих числа \(n\) та \(m\) — кількість злочинців та запитів відповідно.
У другому рядку задано через пробіли \(n\) цілих чисел \(h_1, \ldots, h_n\) — початкові рівні здоров’я злочинців.
У наступних \(m\) рядках задано запити у форматі, наведеному вище. Запити потрібно виконувати в тому порядку, у якому вони задані.
Вихідні дані
Для кожного запиту третього типу виведіть одне ціле число — відповідь до цього запиту.
Обмеження
\(1 \le n, m \le 2\cdot10^5\),
\(1 \le h_i \le 10^9\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 7 4 1 3 4 Q 2 L 2 R 3 Q 1 Q 2 Q 3 Q 4 | 1 3 0 2 3 |
Примітки
Після другого запиту рівні здоров’я злочинців будуть [3, 0, 3, 4]. Після третього — [3, 0, 2, 3].
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|