http://poj.org/problem?id=2823
注意G++会TLE。
用pair<int,int>数组模拟deque即可
完整代码：
/*5360ms,19272KB*/
#include<cstdio>
#include<cstring>
#include<utility>
using namespace std;
const int mx = 1000005;
pair<int, int> minq[mx], maxq[mx]; /// first表示值，second表示该值在原序列的位置
int maxans[mx];
int minhead, mintail, maxhead, maxtail;
void push(int x, int i)
{
/// minq.push(x)
if (mintail != minhead)
while (mintail != minhead && x <= minq[mintail].first) --mintail;
minq[++mintail] = make_pair(x, i);
/// maxq.push(x)
if (maxtail != maxhead)
while (maxtail != maxhead && x >= maxq[maxtail].first) --maxtail;
maxq[++maxtail] = make_pair(x, i);
}
int main()
{
int n, k, i, j = 1, x, cnt = 0;
scanf("%d%d", &n, &k);
for (i = 0; i < k; ++i)
{
scanf("%d", &x);
push(x, i);
}
printf("%d", minq[minhead + 1].second == 0 ? minq[++minhead].first : minq[minhead + 1].first);
maxans[cnt++] = (maxq[maxhead + 1].second == 0 ? maxq[++maxhead].first : maxq[maxhead + 1].first);
for (; i < n; ++i, ++j)
{
scanf("%d", &x);
push(x, i);
printf(" %d", minq[minhead + 1].second == j ? minq[++minhead].first : minq[minhead + 1].first);
maxans[cnt++] = (maxq[maxhead + 1].second == j ? maxq[++maxhead].first : maxq[maxhead + 1].first);
}
printf("\n%d", maxans[0]);
for (i = 1; i < cnt; ++i) printf(" %d", maxans[i]);
putchar(10);
return 0;
}