К-та порядкова статистика
Обмеження: 1 сек., 256 МіБ
Дано порожній масив \(A\) і багато запитів \(Q\). Запити бувають 3-ох типів:
1 \(x\) — вставити елемент зі значенням \(x\) в масив \(A\)
2 \(x\) — видалити елемент зі значенням \(x\) з масиву \(A\). Гарантується, що елемент \(x\) знаходиться в масиві \(A\).
3 \(K\) — порахувати \(K\)-у порядкову статистику масиву \(A\).
Для кожного запиту 3-го типу виведіть результат виконання цього запиту.
Гарантується, що всі елементи, які вставляються в масив \(A\) різні.
Вхідні дані
У першому рядку задано число \(Q\) — кількість запитів в задачі.
У наступних \(Q\) рядках задано запити у форматі \(t\) \(x\), де \(t\) — тип запиту (\(1\), \(2\) або \(3\)), а \(x\) — це значення елементу для запиту типів \(1\) та \(2\), або значення \(K\) для запиту типу \(3\).
Вихідні дані
Для кожного запиту типу \(3\) виведіть в новому рядку значення \(K\)-ої порядкової статистики в масиві \(A\) на даний момент.
Обмеження
\(1 \le Q \le 10^5\),
\(1 \le t \le 3\),
для \(t=1\) або \(t=2\): \(1 \le x \le 10^9\),
для \(t=3\): \(1 \le x \le |A|\), де \(|A|\) — розмір масиву \(A\) на даний момент.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
5 1 1 3 1 1 4 1 2 3 2 | 1 2 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
6 1 1 1 3 1 2 3 2 2 2 3 2 | 2 3 |
Примітки
\(K\)-та порядкова статистика, це елемент, який буде \(K\)-им за рахунком в масиві, якщо його елементи відсортувати в порядку зростання.
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|