水人从不用正解qwq
蒟蒻思路: 把 vector 当作一个优先队列,入队和出队虽不如优先队列快,但访问却很快。
code:
#include <bits/stdc++.h>
using namespace std;
queue < int > q1, q2;
vector < int > q;
const int N = 1e6 + 5;
int n, m, a[N];
signed main()
{
ios::sync_with_stdio (false);
cin.tie (0); cout.tie (0);
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
q.insert (lower_bound (q.begin(), q.end(), a[i]), a[i]);
if (i > m)
{
q.erase (lower_bound (q.begin(), q.end(), a[i - m]));
}
if (i >= m)
{
q1.push (q[0]);
q2.push (q[q.size() - 1]);
}
}
while (!q1.empty())
{
cout << q1.front() << " ";
q1.pop();
}
cout << endl;
while (!q2.empty())
{
cout << q2.front() << " ";
q2.pop();
}
return 0;
}
为什么不打注释!!
Orz