Задача №115411. Порядковая статистика
- Выбрать \(i_1\), \(i_2\), \(\ldots\), \(i_k\) — позиции \(k\) наибольших элементов в массиве \(a\). При равенстве двух элементов большим считается элемент, стоящий в массиве на меньшей позиции.
- Уменьшить \(a_{i_1}\), \(a_{i_2}\), \(\ldots\), \(a_{i_k}\) на \(1\).
Для \(x\) от \(1\) до \(n\), обозначим через \(F_{m,k}(x)\) значение \(x\)-й порядковой статистики в массиве, получаемом из \(a\) применением \(m\) раз операции с заданным параметром \(k\). Для \(x\) от \(1\) до \(n\), \(x\)-й порядковой статистикой массива \(a_1,a_2,\ldots,a_n\) называется элемент, который будет стоять на позиции \(x\), если массив \(a\) отсортировать в порядке неубывания.
Для всех \(l, r\), таких, что \(1 \le l \le r \le n\), обозначим через \(S_{m,k}(l,r)\) сумму \(F_{m,k}(x)\) по всем целым \(x\) от \(l\) до \(r\). Более формально: \(\) S_{m,k}(l,r)=\sum_{x=l}^r F_{m,k}(x) \(\) Вам даны целые числа \(m_0\) и \(k_0\). Вы должны вычислить для всех \(x\) от \(1\) до \(n\) значения \(F_{m_0,k_0}(x)\).
После этого вы должны обработать \(q\) запросов. \(j\)-й запрос (\(1 \le j \le q\)) может быть одного из трех типов:
- Вычислить значение \(F_{m_j,k_j}(x_j)\).
- Изменить значение \(a_{p_j}\) на \(v_j\).
- Вычислить значение \(S_{m_j,k_j}(l_j,r_j)\).
Все вычисления функций \(F\) и \(S\) производятся каждый раз независимо и не меняют массив. Все изменения массива в запросах второго типа сохраняются для следующих запросов.
Первая строка содержит четыре целых числа \(n\), \(m_0\), \(k_0\) и \(q\) (\(1 \le n \le 200\,000\), \(0 \le m_0 \le 10^9\), \(1 \le k_0 \le n\), \(0 \le q \le 200\,000\)) — длина массива \(a\); количество операций; количество наибольших элементов, уменьшаемых на каждой операции, и количество запросов.
Вторая строка содержит \(n\) целых чисел \(a_1,\ a_2,\ \ldots,\ a_n\) (\(-10^9 \le a_i \le 10^9\), \(1 \le i \le n\)) — элементы массива \(a\).
В следующих \(q\) строках заданы запросы. В \(j\)-й из них в начале содержится число \(t_j\) (\(1 \le t_j \le 3\)) — тип \(j\)-го запроса.
- Если \(t_j=1\), то далее строка содержит три целых числа \(m_j\), \(k_j\) и \(x_j\) (\(0 \le m_j \le 10^9\), \(1 \le k_j,x_j \le n\)) — параметры запроса первого типа.
- Если \(t_j=2\), то далее строка содержит два целых числа \(p_j\) и \(v_j\) (\(1 \le p_j \le n\), \(-10^9 \le v_j \le 10^9\)) — параметры запроса второго типа.
- Если \(t_j=3\), то далее строка содержит четыре целых числа \(m_j\), \(k_j\), \(l_j\) и \(r_j\) (\(0 \le m_j \le 10^9\), \(1 \le k_j,l_j,r_j \le n\), \(l_j \le r_j\)) — параметры запроса третьего типа.
В первой строке выведите \(n\) целых чисел \(F_{m_0,k_0}(1),F_{m_0,k_0}(2),\ldots,F_{m_0,k_0}(n)\).
Далее, для каждого запроса первого типа выведите в отдельной строке значение \(F_{m_j, k_j}(x_j)\), а для каждого запроса третьего типа значение \(S_{m_j,k_j}(l_j,r_j)\) — ответ на \(j\)-й запрос.
В примере \(n=8\), \(m_0=3\), \(k_0=2\), \(q=16\). Изначально массив \(a\) равен \([3, 1, 2, -1, 0, 2, -1, 4]\). Посмотрим, как массив будет меняться, если применить к нему \(m_0\) раз операцию с параметром \(k_0\):
- Массив равен \([3,1,2,-1,0,2,-1,4]\). Два наибольших элемента стоят на позициях \(1\) и \(8\). Они уменьшаются на \(1\), после чего массив становится равен \([2,1,2,-1,0,2,-1,3]\).
- Массив равен \([2,1,2,-1,0,2,-1,3]\). Два наибольших элемента стоят на позициях \(1\) и \(8\). Они уменьшаются на \(1\), после чего массив становится равен \([1,1,2,-1,0,2,-1,2]\).
- Массив равен \([1,1,2,-1,0,2,-1,2]\). Два наибольших элемента стоят на позициях \(3\) и \(6\). Они уменьшаются на \(1\), после чего массив становится равен \([1,1,1,-1,0,1,-1,2]\).
В примере требуется обработать \(16\) запросов, разберем подробно первые \(10\) из них:
- Первый запрос имеет тип \(t_1=3\), параметры \(m_1=3\), \(k_1=2\), \(l_1=2\), \(r_1=6\) и требует вычислить значение \(S_{3,2}(2,6)\). Ранее мы уже вычислили значения \(F_{3,2}(x)\) для \(x\) от \(1\) до \(8\), откуда находим ответ на запрос: \(\) S_{3,2}(2,6)=F_{3,2}(2)+F_{3,2}(3)+F_{3,2}(4)+F_{3,2}(5)+F_{3,2}(6)= (-1)+0+1+1+1=2 \(\)
- Второй запрос имеет тип \(t_2=1\), параметры \(m_2=3\), \(k_2=2\), \(x_2=4\) и требует вычислить значение \(F_{3,2}(4)\). Его мы уже вычисляли, оно равно \(1\).
- Третий запрос имеет тип \(t_3=3\), параметры \(m_3=4\), \(k_3=5\), \(l_3=3\), \(r_3=5\) и требует вычислить значение \(S_{4,5}(3,5)\), то есть посчитать сумму порядковых статистик с третьей по пятую в массиве, полученном из \(a\) применением \(m_3=4\) раза операции с параметром \(k_3=5\). На момент третьего запроса массив \(a\) равен \([3, 1, 2, -1, 0, 2, -1, 4]\). Пять наибольших элементов стоят на позициях \(1,2,3,6,8\). Уменьшим их на \(1\), получим массив \([2,0,1,-1,0,1,-1,3]\). Применим операцию еще три раза, получим массив \([-1,-2,-2,-2,-1,-1,-1,0]\). После сортировки он равен \([-2,-2,-2,-1,-1,-1,-1,0]\). Получаем, что ответ на запрос равен \(\) S_{4,5}(3,5)=F_{4,5}(3)+F_{4,5}(4)+F_{4,5}(5)=(-2)+(-1)+(-1)=-4 \(\)
- Четвертый запрос имеет тип \(t_4=1\), параметры \(m_4=4\), \(k_4=5\), \(x_4=6\). После применения четырех операций с параметром \(5\) и сортировки массив \(a\) будет равен \([-2,-2,-2,-1,-1,-1,-1,0]\), поэтому шестая порядковая статистика равна \(-1\).
- Пятый запрос имеет тип \(t_5=2\), параметры \(p_5=5\) и \(v_5=-1\). Он меняет значение \(a_5\) на \(-1\), после чего массив \(a\) становится равен \([3,1,2,-1,-1,2,-1,4]\).
- Шестой запрос имеет тип \(t_6=2\), параметры \(p_6=6\) и \(v_6=3\). Он меняет значение \(a_6\) на \(3\), после чего массив \(a\) становится равен \([3,1,2,-1,-1,3,-1,4]\).
- Седьмой запрос требует найти значение \(F_{3,2}(1)\). Массив \(a\) на момент седьмого запроса равен \([3,1,2,-1,-1,3,-1,4]\). После применения \(3\) раза операции с параметром \(2\) он будет равен \([1, 1, 1, -1, -1, 2, -1, 2]\). Первая порядковая статистика этого массива равна \(-1\).
- Восьмой, девятый и десятый запросы требуют найти значения \(F_{3,2}(3)\), \(F_{3,2}(4)\) и \(F_{3,2}(8)\), то есть третью, четвертую и восьмую порядковые статистики в массиве \([1, 1, 1, -1, -1, 2, -1, 2]\). Они равны соответственно \(-1\), \(1\) и \(2\).
Тесты к этой задаче состоят из двенадцати групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
Если в подзадаче указаны ограничения на \(m\) или \(k\), то они распространяются как на \(m_0\) и \(k_0\), так и на параметры всех запросов первого и третьего типов.
| Доп. ограничения | |||||||
| Группа | Баллы | \(n\) | \(m\) | \(k\) | \(q\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | – | Тесты из условия. |
| 1 | 4 | \(n \le 1000\) | \(m \le 1000\) | – | \(q=0\) | – | – |
| 2 | 5 | – | – | \(k=1\) | \(q=0\) | – | – |
| 3 | 6 | – | – | \(k=1\) | \(q \le 100\,000\) | 2 | \(t_j=1\) для всех запросов |
| 4 | 7 | – | – | \(k=1\) | \(q \le 100\,000\) | 2, 3 | \(t_j \ne 3\) для всех запросов |
| 5 | 11 | – | – | \(k=2\) | \(q=0\) | – | – |
| 6 | 9 | – | \(m \le 10^6\) | – | \(q=0\) | 1 | – |
| 7 | 10 | \(n \le 1000\) | – | – | \(q=0\) | 1 | – |
| 8 | 7 | – | – | – | \(q=0\) | 1, 2, 5 – 7 | – |
| 9 | 11 | – | – | – | \(q \le 100\,000\) | 1 – 3, 5 – 8 | \(t_j=1\) для всех запросов |
| 10 | 13 | – | – | – | \(q \le 100\,000\) | 1 – 3, 5 – 9 | \(t_j\ne 2\) для всех запросов |
| 11 | 9 | – | – | – | \(q \le 100\,000\) | 0 – 10 | – |
| 12 | 8 | – | – | – | – | 0 – 11 | Offline-проверка. |
8 3 2 16 3 1 2 -1 0 2 -1 4 3 3 2 2 6 1 3 2 4 3 4 5 3 5 1 4 5 6 2 5 -1 2 6 3 1 3 2 1 1 3 2 3 1 3 2 4 1 3 2 8 1 0 5 6 2 1 5 3 1 3 7 8 3 2 3 5 8 3 3 3 4 7 3 4 3 4 7
-1 -1 0 1 1 1 1 2 2 1 -4 -1 -1 -1 1 2 3 7 8 4 2