Задача №114765. Экспедиция на Сириус
В компьютерную игру «Экспедиция на Сириус» играют \(n\) игроков, пронумерованных от \(1\) до \(n\). За предыдущие миссии у игрока номер \(i\) накоплено \(c_i\) единиц опыта. Будем говорить, что два игрока имеют одинаковый уровень , если у них одинаковое значение опыта. Игрок, который имеет больше опыта, имеет более высокий уровень.
Игра состоит из нескольких раундов. В конце каждого раунда каждому игроку добавляется опыт, равный количеству различных более высоких уровней у остальных игроков. Например, если значения опыта игроков \([2, 5, 5, 1, 2, 10]\), то опыт первого игрока увеличится на 2: существует два более высоких уровня — игроки с опытом 5 и игрок с опытом 10. Опыт последнего игрока в этом примере не увеличится. Опыт игроков изменяется одновременно. То есть в конце раунда в нашем примере опыт игроков станет равным \([4, 6, 6, 4, 4, 10]\).
Вам требуется ответить на несколько вопросов. Каждый вопрос может быть одного из трех типов:
- Сколько различных уровней будет у игроков после \(k\) раундов игры?
- Какое суммарное количество единиц опыта добавится всем игрокам за первые \(k\) раундов?
- Сколько единиц опыта будет у игрока номер \(i\) после начисления опыта в конце \(k\)-го раунда?
В первой строке даны два целых числа \(n\) и \(q\) (\(1 \le n, q \le 300\,000)\) — количество игроков и количество вопросов, на которые вам нужно ответить.
Во второй строке даны \(n\) целых чисел \(c_i\) (\(0 \le c_i \le 10^{12}\)) — количество единиц опыта у каждого из игроков в начале текущей игры.
В следующих \(q\) строках даны описания вопросов. Каждая строка начинается с целого числа \(t\) (\(t \in \{1, 2, 3\}\)), которое обозначает тип вопроса.
- Если \(t = 1\), далее дано целое число \(k\) (\(0 \le k \le 10^{12}\)) — количество раундов.
- Если \(t = 2\), далее дано целое число \(k\) (\(0 \le k \le 10^{12}\)) — количество раундов.
- Если \(t = 3\), далее даны два целых числа \(k\) и \(i\) (\(0 \le k \le 10^{12}\), \(1 \le i \le n\)) — количество раундов и номер игрока, опыт которого нас интересует.
Во всех вопросах \(k = 0\) означает момент начала игры до проведения первого раунда.
Для каждого вопроса выведите ответ на него в новой строке.
Пусть для всех тестов в подзадаче выполнено \(n \le N_{max}\), \(q \le Q_{max}\), \(c_i \le C_{max}\), \(k \le K_{max}\).
| Ограничения | |||||||
| Подзадача | Баллы | \(N_{max}\) | \(Q_{max}\) | \(C_{max}\), \(K_{max}\) | \(t\) | Необх. подзадачи | Информация о проверке |
| 1 | 18 | \(5000\) | \(5000\) | \(10\,000\) | У | первая ошибка | |
| 2 | 16 | \(5000\) | \(5000\) | \(10^7\) | У, 1 | первая ошибка | |
| 3 | 14 | \(5000\) | \(5000\) | \(10^{12}\) | У, 1, 2 | первая ошибка | |
| 4 | 7 | \(3 \cdot 10^5\) | \(3 \cdot 10^5\) | \(10^7\) | У, 1, 2 | первая ошибка | |
| 5 | 12 | \(5000\) | \(3 \cdot 10^5\) | \(10^{12}\) | У, 1–3 | первая ошибка | |
| 6 | 14 | \(3 \cdot 10^5\) | \(3 \cdot 10^5\) | \(10^{12}\) | \(t=1\) | первая ошибка | |
| 7 | 10 | \(3 \cdot 10^5\) | \(3 \cdot 10^5\) | \(10^{12}\) | \(t\in\{1,2\}\) | 6 | первая ошибка |
| 8 | 9 | \(3 \cdot 10^5\) | \(3 \cdot 10^5\) | \(10^{12}\) | У, 1–7 | первая ошибка | |
В первом тесте опыт игроков изменяется следующим образом:
| Раунд | \(c_1\) | \(c_2\) | \(c_3\) | \(c_4\) | \(c_5\) | \(c_6\) |
| начало игры | 5 | 4 | 4 | 2 | 2 | 2 |
| 1 | 5 | 5 | 5 | 4 | 4 | 4 |
| 2 | 5 | 5 | 5 | 5 | 5 | 5 |
Во втором тесте опыт игроков изменяется следующим образом:
| Раунд | \(c_1\) | \(c_2\) | \(c_3\) | \(c_4\) | \(c_5\) |
| начало игры | 0 | 3 | 5 | 4 | 2 |
| 1 | 4 | 5 | 5 | 5 | 5 |
6 6 5 4 4 2 2 2 1 0 1 1 1 2 2 1 2 2 3 1 5
3 2 1 8 11 4
5 4 0 3 5 4 2 1 0 1 1 2 1 3 1 1
5 2 10 4