off-line minimum problem - llhuii's Blog

 The off-line minimum problem asks us to maintain a dynamic set of elements from the domain under the operations INSERT and EXTRACT-MIN. We are given a sequence S of n INSERT and m EXTRACT-MIN calls, where each key in is inserted exactly once. We wish to determine which key is returned by each EXTRACT-MIN call. Specifically, we wish to fill in an array , where for is the key returned by the th EXTRACT-MIN call.
static int[] offlineMinimum(int[] A, int[] E) {
int[] R = new int[A.length];
Arrays.fill(R, E.length);
int pre = 0;

// Initialize the collection of subsets.
for (int i = 0; i < E.length; ++i) {
for (int j = pre; j <= E[i]; ++j) {
R[A[j]] = i;
}
pre = E[i] + 1;
}

int[] ret = new int[E.length];
Arrays.fill(ret, -1); // stores the answer
int[] set = new int[E.length + 1]; // the disjoint-set
iota(set, 0, set.length, 0); // initializes the disjoint-set
for (int i = 0; i < A.length; ++i) {
if (findSet(set, R[i]) != E.length && ret[findSet(set, R[i])] == -1) {
ret[set[R[i]]] = i;
unionSet(set, set[R[i]], set[R[i]] + 1);
}
}
return ret;
}
Read full article from off-line minimum problem - llhuii's Blog