Maintain the multiset of inserted values with a Fenwick tree over the fixed value domain [1, 2_000_000]. tree[i] stores the frequency sum for the range ending at i determined by the low bit i & -i. Inserting a value adds one to its frequency; removing a rank first finds the corresponding value and then subtracts one, so equal values remain separate occurrences.
To select the k-th smallest value, Fenwick binary lifting builds the answer from the largest power of two downward. At each step it skips a candidate prefix only when its frequency is less than the remaining rank, subtracting that prefix count from k. The final index is the value whose cumulative frequency first reaches the original rank. This works for the first and last valid ranks, including when frequencies are duplicated. Each insertion, selection, and removal takes O(log V) time, where V = 2_000_000; the tree uses O(V) space. Counts fit in int because the number of operations is bounded by the problem input.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.io.BufferedInputStream;
import java.io.IOException;
public class Main {
private static final int MAX_VALUE = 2_000_000;
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
int operationCount = input.nextInt();
FenwickTree frequencies = new FenwickTree(MAX_VALUE);
StringBuilder output = new StringBuilder();
for (int i = 0; i < operationCount; i++) {
int operation = input.nextInt();
int valueOrRank = input.nextInt();
if (operation == 1) {
frequencies.add(valueOrRank, 1);
} else {
int value = frequencies.kth(valueOrRank);
output.append(value).append('\n');
frequencies.add(value, -1);
}
}
System.out.print(output);
}
private static final class FenwickTree {
private final int[] tree;
FenwickTree(int size) {
tree = new int[size + 1];
}
void add(int index, int delta) {
for (int i = index; i < tree.length; i += i & -i) {
tree[i] += delta;
}
}
int kth(int rank) {
int index = 0;
for (int step = Integer.highestOneBit(tree.length - 1); step != 0; step >>= 1) {
int next = index + step;
if (next < tree.length && tree[next] < rank) {
index = next;
rank -= tree[next];
}
}
return index + 1;
}
}
private static final class FastScanner {
private final BufferedInputStream input = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int length;
private int position;
private int read() throws IOException {
if (position == length) {
length = input.read(buffer);
position = 0;
if (length == -1) {
return -1;
}
}
return buffer[position++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
}