|
Description 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; Let us examine a possible sequence of 11 transactions: Example 1 N Transaction i Black Box contents after transaction Answer 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 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. Output Write to the output Black Box answers sequence for a given sequence of transactions, one number each line. Sample Input 7 4 Sample Output 3 Source |
【分析】
练下手而已，没什么。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <queue>
#include <assert.h>
#include <map> const int N = + ;
const int SIZE = ;//块状链表的大小
const int M = + ;
using namespace std;
struct TREAP{
struct Node{
int fix, size;
int val;
Node *ch[];
}mem[ + ], *root;
int tot;
//大随机
int BIG_RAND(){return (rand() * RAND_MAX + rand());}
Node *NEW(){
Node *p = &mem[tot++];
p->fix = BIG_RAND();
p->val = ;
p->size = ;
p->ch[] = p->ch[] = NULL;
return p;
}
//将t的d节点换到t
void rotate(Node *&t, int d){
Node *p = t->ch[d];
t->ch[d] = p->ch[d ^ ];
p->ch[d ^ ] = t;
t->size = ;
if (t->ch[] != NULL) t->size += t->ch[]->size;
if (t->ch[] != NULL) t->size += t->ch[]->size;
t = p;
t->size = ;
if (t->ch[] != NULL) t->size += t->ch[]->size;
if (t->ch[] != NULL) t->size += t->ch[]->size;
return;
}
void insert(Node *&t, int val){
//插入
if (t == NULL){
t = NEW();
t->val = val;
return;
}
//大的在右边,小的在左边
int dir = (val >= t->val);
insert(t->ch[dir], val);
//维护最大堆的性质
if (t->ch[dir]->fix > t->fix) rotate(t, dir);
t->size = ;
if (t->ch[] != NULL) t->size += t->ch[]->size;
if (t->ch[] != NULL) t->size += t->ch[]->size;
}
//在t的子树中找到第k小的值
int find(Node *t, int k){
if (t->size == ) return t->val;
int l = ;//t的左子树中有多少值
if (t->ch[] != NULL) l += t->ch[]->size;
if (k == (l + )) return t->val;
if (k <= l) return find(t->ch[], k);
else return find(t->ch[], k - (l + ));
}
}treap;
typedef long long ll;
int have[N];//have为1则在这个地方GET
int data[N], m, n; void init(){
treap.root = NULL;
treap.tot = ;
memset(have, , sizeof(have));
scanf("%d%d", &m, &n);
for (int i = ; i <= m; i++) scanf("%d", &data[i]);
for (int i = ; i <= n; i++){
int x;
scanf("%d", &x);
have[x]++;
}
}
void work(){
int pos = ;//代表要获得的位置
for (int i = ; i <= m; i++){
treap.insert(treap.root, data[i]);
//printf("%d", treap.root->size);
while (have[i]){
pos++;
printf("%d\n", treap.find(treap.root, pos));
have[i]--;
}
} } int main(){
int T;
#ifdef LOCAL
freopen("data.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
init();
work();
return ;
}
