POJ-2823 POJ-3250 (单调队列 单调栈)
poj-2823: 求n个数序列中的所有段长度为k的区间内的最大值和最小值。
poj-3250: 求n个数序列中每个位置的右边的数小于其数值的个数，并且中间不能有大于等于它的数。
poj-2823 下面这份代码只能在c++编译器下才能过，其它编译器超时，其实只需要在出队的时候加个二分优化就能过，但懒得改了，主要是学单调队列的做法。
#include <cstdio>
using namespace std;
const int maxn = 1e6+5;
int a[maxn], ans1[maxn], ans2[maxn];
int q1[maxn], q2[maxn];
int head1, tail1, head2, tail2;
int n, k;
int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d %d", &n, &k);
head1 = tail1 = 0;
head2 = tail2 = 0;
for(int i = 1; i < k; ++i)
{
scanf("%d", &a[i]);
while(head1 < tail1 && a[q1[tail1-1]] >= a[i]) --tail1;
q1[tail1++] = i;
while(head2 < tail2 && a[q2[tail2-1]] <= a[i]) --tail2;
q2[tail2++] = i;
}
for(int i = k; i <= n; ++i)
{
scanf("%d", &a[i]);
while(head1 < tail1 && q1[head1] < i-k+1) ++head1;
while(head1 < tail1 && a[q1[tail1-1]] >= a[i]) --tail1;
q1[tail1++] = i;
while(head2 < tail2 && q2[head2] < i-k+1) ++head2;
while(head2 < tail2 && a[q2[tail2-1]] <= a[i]) --tail2;
q2[tail2++] = i;
ans1[i] = a[q1[head1]];
ans2[i] = a[q2[head2]];
}
for(int i = k; i <= n; ++i)
printf("%d%c", ans1[i], i==n?'\n':' ');
for(int i = k; i <= n; ++i)
printf("%d%c", ans2[i], i==n?'\n':' ');
return 0;
}
poj-3250 自己先写了个丑的单调栈，然后又写了一个跟网上一样的简短代码。
#include <cstdio>
#define ll long long
using namespace std;
const int maxn = 8e4+5;
int n, a[maxn];
int top, sk[maxn];
ll res, ans[maxn];
int main()
{
scanf("%d", &n);
res = 0; top = 0;
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for(int i = n; i >= 1; --i)
{
int tmp = 0;
while(top > 0 && a[sk[top]] < a[i]) tmp += ans[sk[top]], --top;
res += tmp;
ans[i] = tmp+1;
sk[++top] = i;
}
printf("%lld\n", res);
return 0;
}
#include <cstdio>
#define ll long long
using namespace std;
const int maxn = 8e4+5;
int n, a[maxn];
int top, sk[maxn];
ll ans;
int main()
{
scanf("%d", &n);
ans = 0; top = 0;
for(int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
while(top > 0 && a[sk[top]] <= a[i]) --top;
ans += top;
sk[++top] = i;
}
printf("%lld\n", ans);
return 0;
}
继续加油~