К-та порядкова статистика
Limits: 1 sec., 256 MiB
Дано порожній масив \(A\) і багато запитів \(Q\). Запити бувають 3-ох типів:
1 \(x\) — вставити елемент зі значенням \(x\) в масив \(A\)
2 \(x\) — видалити елемент зі значенням \(x\) з масиву \(A\). Гарантується, що елемент \(x\) знаходиться в масиві \(A\).
3 \(K\) — порахувати \(K\)-у порядкову статистику масиву \(A\).
Для кожного запиту 3-го типу виведіть результат виконання цього запиту.
Гарантується, що всі елементи, які вставляються в масив \(A\) різні.
Input
У першому рядку задано число \(Q\) — кількість запитів в задачі.
У наступних \(Q\) рядках задано запити у форматі \(t\) \(x\), де \(t\) — тип запиту (\(1\), \(2\) або \(3\)), а \(x\) — це значення елементу для запиту типів \(1\) та \(2\), або значення \(K\) для запиту типу \(3\).
Output
Для кожного запиту типу \(3\) виведіть в новому рядку значення \(K\)-ої порядкової статистики в масиві \(A\) на даний момент.
Constraints
\(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\) на даний момент.
Samples
Input (stdin) | Output (stdout) |
---|---|
5 1 1 3 1 1 4 1 2 3 2 | 1 2 |
Input (stdin) | Output (stdout) |
---|---|
6 1 1 1 3 1 2 3 2 2 2 3 2 | 2 3 |
Notes
\(K\)-та порядкова статистика, це елемент, який буде \(K\)-им за рахунком в масиві, якщо його елементи відсортувати в порядку зростання.
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|