| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 125 | 27 | 22 | 19.469% |
В компьютерную игру <<Экспедиция на Сириус>> играют $n$ игроков, пронумерованных от 1ドル$ до $n$. За предыдущие миссии у игрока номер $i$ накоплено $c_i$ единиц опыта. Будем говорить, что два игрока имеют одинаковый уровень, если у них одинаковое значение опыта. Игрок, который имеет больше опыта, имеет более высокий уровень.
Игра состоит из нескольких раундов. В конце каждого раунда каждому игроку добавляется опыт, равный количеству различных более высоких уровней у остальных игроков. Например, если значения опыта игроков $[2, 5, 5, 1, 2, 10],ドル то опыт первого игрока увеличится на 2: существует два более высоких уровня --- игроки с опытом 5 и игрок с опытом 10. Опыт последнего игрока в этом примере не увеличится. Опыт игроков изменяется одновременно. То есть в конце раунда в нашем примере опыт игроков станет равным $[4, 6, 6, 4, 4, 10]$.
Вам требуется ответить на несколько вопросов. Каждый вопрос может быть одного из трех типов:
В первой строке даны два целых числа $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\}$), которое обозначает тип вопроса.
Во всех вопросах $k = 0$ означает момент начала игры до проведения первого раунда.
Для каждого вопроса выведите ответ на него в новой строке.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 18 | $n \le 5000,ドル $q \le 5000,ドル $c_i, k \le 10,000円$ |
| 2 | 16 | $n \le 5000,ドル $q \le 5000,ドル $c_i, k \le 10^7$ |
| 3 | 14 | $n \le 5000,ドル $q \le 5000,ドル $c_i, k \le 10^{12}$ |
| 4 | 7 | $n \le 3 \cdot 10^5,ドル $q \le 3 \cdot 10^5,ドル $c_i, k \le 10^7$ |
| 5 | 12 | $n \le 5000,ドル $q \le 3 \cdot 10^5,ドル $c_i, k \le 10^{12}$ |
| 6 | 14 | $n \le 3 \cdot 10^5,ドル $q \le 3 \cdot 10^5,ドル $c_i, k \le 10^{12},ドル $t = 1$ |
| 7 | 10 | $n \le 3 \cdot 10^5,ドル $q \le 3 \cdot 10^5,ドル $c_i, k \le 10^{12},ドル $t\in\{1,2\}$ |
| 8 | 9 | $n \le 3 \cdot 10^5,ドル $q \le 3 \cdot 10^5,ドル $c_i, k \le 10^{12}$ |
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
В первом тесте опыт игроков изменяется следующим образом:
| Раунд | $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 |