算法题：Black Box

问题描述

Our Black Box represents a primitive database. It can save an integer array and has a special i variable. At the initial moment Black Box is empty and i equals 0. This Black Box processes a sequence of commands (transactions). There are two types of transactions:
ADD (x): put element x into Black Box;
GET: increase i by 1 and give an i-minimum out of all integers containing in the Black Box. Keep in mind that i-minimum is a number located at i-th place after Black Box elements sorting by non- descending.
Let us examine a possible sequence of 11 transactions:
| N | Transaction | i | Black Box contents after transaction | Answer |
| ---- | ----------- | ---- | ------------------------------------ | ------ |
| 1 | ADD(3) | 0 | 3 | |
| 2 | GET | 1 | 3 | 3 |
| 3 | ADD(1) | 1 | 1,3 | |
| 4 | GET | 2 | 1,3 | 3 |
| 5 | ADD(-4) | 2 | -4,1,3 | |
| 6 | ADD(2) | 2 | -4,1,2,3 | |
| 7 | ADD(8) | 2 | -4,1,2,3,8 | |
| 8 | ADD(-1000) | 2 | -1000,-4,1,2,3,8 | |
| 9 | GET | 3 | -1000,-4,1,2,3,8 | 1 |
| 10 | GET | 4 | -1000,-4,1,2,3,8 | 2 |
| 11 | ADD(2) | 4 | -1000,-4,1,2,2,3,8 | |
It is required to work out an efficient algorithm which treats a given sequence of transactions. The maximum number of ADD and GET transactions: 30000 of each type.
Let us describe the sequence of transactions by two integer arrays:

1. A(1),A(2),…,A(M): a sequence of elements which are being included into Black Box. A values are integers not exceeding 2 000 000 000 by their absolute value, M≤30000. For the Example we have A=(3,1,−4,2,8,−1000,2).
2. u(1),u(2),...,u(N): a sequence setting a number of elements which are being included into Black Box at the moment of first, second, ... and N-transaction GET. For the Example we have u=(1,2,6,6).
   The Black Box algorithm supposes that natural number sequence u(1),u(2),…,u(N) is sorted in non-descending order, N≤M and for each p (1≤p≤N) an inequality p≤u(p)≤M is valid. It follows from the fact that for the p-element of our u sequence we perform a GET transaction giving p-minimum number from our A(1),A(2),…,A(u(p)) sequence.

输入格式

Input contains (in given order): M,N,A(1),A(2),…,A(M),u(1),u(2),…,u(N). All numbers are divided by spaces and (or) carriage return characters.

输出格式

Write to the output Black Box answers sequence for a given sequence of transactions, one number each line.

样例

输入

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

输出

3
3
1
2

解决方案

思路

二叉堆

代码

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

priority_queue<int, vector<int>, greater<int>> qmin;    //小顶堆
priority_queue<int, vector<int>, less<int>> qmax;       //大顶堆
int arr[30005], k = 0;

void input(int v) {
    if (qmax.empty() || v <= qmax.top()) qmax.push(v);
    else qmin.push(v);
}

void trans(int pos) {
    while (pos < qmax.size()) {
        qmin.push(qmax.top());
        qmax.pop();
    }
    while (pos > qmax.size()) {
        qmax.push(qmin.top());
        qmin.pop();
    }
}

int main() {
    int m, n;
    cin >> m >> n;

    for (int i = 0; i < m; ++i) {
        int t;
        cin >> t;
        arr[i] = t;
    }

    for (int i = 1; i <= n; ++i) {
        int t;
        cin >> t;

        while (k < t) input(arr[k++]);
        trans(i);

        cout << qmax.top() << endl;
    }

    return 0;
}