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. 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
3 1 -4 2 8 -1000 2
1 2 6 6
Sample Output
3
3
1
2
Source
题目类型：动态查询区间第k小
算法分析：直接使用Treap边插入，边查询即可，注意如果查询出现在插入完所有元素之后的话，此时要注意循环的判出条件！！！
|
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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long #define DB(ccc) cout << #ccc << " = " << ccc << endl const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 3e4 + 66; struct node { int l, r, v, size, rnd, w; }tr[maxn]; //分别表示节点的个数、标号变量、根节点和最终的结果 int n, size, root; void Init () { root = size = 0; memset (tr, 0, sizeof (tr)); } void UpDate (int rt)//更新结点信息 { tr[rt].size = tr[tr[rt].l].size + tr[tr[rt].r].size + tr[rt].w; } void lturn (int &rt) { int tt = tr[rt].r; tr[rt].r = tr[tt].l; tr[tt].l = rt; tr[tt].size = tr[rt].size; UpDate(rt); rt = tt; } void rturn (int &rt) { int tt = tr[rt].l; tr[rt].l = tr[tt].r; tr[tt].r = rt; tr[tt].size = tr[rt].size; UpDate(rt); rt = tt; } void Insert (int &rt, int x) { if (rt == 0) { rt = ++size; tr[rt].size = tr[rt].w = 1; tr[rt].v = x; tr[rt].rnd = rand(); return ; } tr[rt].size++; if (tr[rt].v == x) tr[rt].w++;//每个结点顺便记录下与该节点相同值的数的个数 else if (x > tr[rt].v) { Insert (tr[rt].r, x); if (tr[tr[rt].r].rnd < tr[rt].rnd) lturn (rt);//维护堆性质 } else { Insert (tr[rt].l, x); if (tr[tr[rt].l].rnd < tr[rt].rnd) rturn (rt); } } int QueryNum (int rt, int x) { if (rt == 0) return 0; if (x <= tr[tr[rt].l].size) return QueryNum (tr[rt].l, x); else if (x > tr[tr[rt].l].size + tr[rt].w) return QueryNum (tr[rt].r, x - tr[tr[rt].l].size - tr[rt].w); else return tr[rt].v; } int a[maxn], u[maxn]; int main() { // CPPFF; int m; while (cin >> n >> m) { Init (); for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= m; i++) cin >> u[i]; for (int pa = 1, pb = 1, all = 0; pb <= m; ) { if (u[pb] == all) { cout << QueryNum(root, pb) << endl; pb++; } else { Insert(root, a[pa]); all++; pa++; } } } return 0; } |
- « 上一篇：poj1365
- poj1456：下一篇 »