训练赛20190304 K - Black Box

这个题的难度主要在于~~反人类的输入~~读题 ## 题面 有一个数组和一个变量i，i初始为0 有两个指令 ADD(x)：向数组中放入一个x GET：i加一，然后查询数组中的第i小 ## 输入 M, N, A(1), A(2), ..., A(M), u(1), u(2), ..., u(N) **其中，A(i)为第i次执行ADD命令时的参数，u(i)为在第u(i)次ADD后执行第i次GET**（这里大概把挺多人绕晕了） ## 输出 每次GET查询的结果 ## 关于输入 以样例输入为例 A = {3 1 -4 2 8 -1000 2} u = {1 2 6 6} 就是在第一次，第二次ADD后各执行一次GET，在第6次ADD后执行两次GET ## 题解 这个题乍一看好像是个区间第K大的题，但其实完全不用那么麻烦（这个题整体数据量不是很大而且只有加入新元素没有修改），开俩堆就能解决。 初始化一个大顶堆left和一个小顶堆right，在每次ADD后，维护这两个堆，使left中保存数组中前i小的元素，right则保存更大的元素。在由于get使i加一之后，right堆的堆顶就是第i小的数。 ```cpp #include<iostream> #include<algorithm> #include<queue> #include<string> #include<vector> #pragma warning(disable:4996) using namespace std; typedef long long ll; #define FOR(i,b,e) for(ll i = b;i<=e;i++) #define INT64_MAX 9223372036854775807 #define INT64_MIN -9223372036854775807 priority_queue<ll>tool_left; priority_queue<ll, vector<ll>, greater<ll> > tool_right; ll n; ll a[30010]; ll a_i = 1; ll u[30010]; ll u_i = 1; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll m, n, it = 0; bool fis = true; cin >> m >> n; FOR(i, 1, m)cin >> a[i]; FOR(i, 1, n) cin >> u[i]; while (a_i <= m) { if (fis) { tool_right.push(a[a_i]); fis = false; }//特判第一次 else {//保证tool_left中所有值都小于tool_right ll rul = (tool_left.size() > 0 ? tool_left.top(): tool_right.top()); if (rul < a[a_i])tool_right.push(a[a_i]); else tool_left.push(a[a_i]); } while (tool_left.size() < it) { ll np = tool_right.top(); tool_right.pop(); tool_left.push(np); } while (tool_left.size() > it) { ll np = tool_left.top(); tool_left.pop(); tool_right.push(np); } while (u[u_i] == a_i) { it++; cout << (tool_right.top()) << endl; //有可能会出现连续多次get的情况，所以get完之后也要更新两个堆 while (tool_left.size() < it) { ll np = tool_right.top(); tool_right.pop(); tool_left.push(np); } while (tool_left.size() > it) { ll np = tool_left.top(); tool_left.pop(); tool_right.push(np); } u_i++; } a_i++; } return 0; } ```