题目链接：http://poj.org/problem?id=2823
用RMQ超时了，我想应该是不会的，看discuss说，之前RMQ过了。
维护两个单调队列。
单调递减的队列，每插入一个时：
超过单调队列长度，左移头指针。
第一个或者符合条件，直接加到后面。
否则，一直退；
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring> using namespace std; const int N = + ; int n,m;
int a[N],q[N]; void MinQ()
{
int h=,t=;
q[] = ;
for(int i=;i<=n;i++) {
if(i-q[h]==m) h++; if(t==h-||a[i]>a[q[t]]) {
t++;
q[t] = i;
}
else {
while(t>=h&&a[i]<=a[q[t]])
{
q[t] = i;
t--;
}
t++;
}
if(i>=m) printf("%d ",a[q[h]]); }
puts("");
} void MaxQ()
{
int h=,t=;
q[] = ;
for(int i=;i<=n;i++) { if(i-q[h]==m) h++; if(t==h-||a[i]<a[q[t]]) {
t++;
q[t] = i;
}
else {
while(t>=h&&a[i]>=a[q[t]])
{
q[t] = i;
t--;
}
t++; }
if(i>=m) printf("%d ",a[q[h]]); }
} int main()
{
cin>>n>>m;
for(int i=;i<=n;i++) {
scanf("%d",&a[i]);
} MinQ();
MaxQ(); return ;
}
题目链接：http://acm.fzu.edu.cn/problem.php?pid=1894
和单调递增队列一样。
/*
RunID: 727738
UserID: TreeDream
Submit time: 2017-02-16 00:04:08
Language: C++
Length: 1167 Bytes.
Result: Accepted
*/ //#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring> using namespace std; const int maxn = + ;
int a[maxn];
int q[maxn]; int main()
{
//freopen("in.txt","r",stdin);
int t;
scanf("%d",&t); while(t--)
{
char op[];
scanf("%s",op); int head = ,tail = ; q[] = -; int i=,j=;
char cmd[],name[];
int len = ; while(scanf("%s",cmd))
{
if(strcmp(cmd,"END")==) break; if(cmd[]=='C') //插入是有条件的
{
scanf("%s",name);
len ++;
scanf("%d",&a[len]);
while(head<=tail&&a[q[tail]]<=a[len])
tail--;
q[++tail] = len;
} else if(cmd[]=='G')
{
while(head<=tail&&q[head]<=j)
head++;
j++;
}
else printf("%d\n",head>tail?-:a[q[head]]);
}
} return ;
}