单调栈及单调队列

单调栈

hdu1506

#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
const ll INF = 1e9;
const ll NUM =1e5+7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x);}
int a[NUM],st[NUM],l[NUM],r[NUM];
int main(){
    int n;
    while(cin>>n){
        if(n==0) break;
        for(int i=1;i<=n;i++) a[i]=read();
        int top=0;
        st[0]=0;//第一个元素的左边第一个比它小的下标是0
        for(int i=1;i<=n;i++){
            while(top&&a[st[top]]>=a[i]) top--;
            l[i]=st[top];
            st[++top]=i;
        }
        top=0;
        st[0]=n+1;//最后一个元素右边第一个比它小的元素下标是n+1
        for(int i=n;i>=1;i--){
            while(top&&a[st[top]]>=a[i]) top--;
            r[i]=st[top];
            st[++top]=i;
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            ans=max(ans,1ll*(r[i]-l[i]-1)*a[i]);
        }
        cout<<ans<<endl;
    }
}

5 2 4 3 1

hdu3410

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7, mod = 1e9 + 7;
typedef long long ll;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int n, a[maxn], st[maxn], top, l[maxn], r[maxn];
int main() {
    int t = read();
    int Case = 1;
    while (t--) {
        n = read();
        for (int i = 1; i <= n; i++) a[i] = read();
        top = 0;
        st[0] = 0;
        for (int i = 1; i <= n; i++) {
            int maxx = -1, k = 0;
            while (top && a[st[top]] < a[i]) {
                if(maxx < a[st[top]]) {
                    maxx = a[st[top]];
                    k = st[top];
                }
                top--;
            }
            l[i] = k;
            st[++top] = i;
        }
        top = 0;
        for (int i = n; i >= 1; i--) {
            int maxx = -1, k = 0;
            while (top && a[st[top]] < a[i]) {
                if(maxx < a[st[top]]) {
                    maxx = a[st[top]];
                    k = st[top];
                }
                top--;
            }
            r[i] = k;
            st[++top] = i;
        }
        printf("Case %d:\n", Case++);
        for (int i = 1; i <= n; i++)
            printf("%d %d\n", l[i], r[i]);
    }
    return 0;
}

//10 9 8 2 3 6 5 7

单调队列
poj2823

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e6 + 7, mod = 1e9 + 7;
typedef long long ll;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int n, k, a[maxn];
int head, tail, que[maxn];
int maxx[maxn], minx[maxn];
int main() {
    n = read(); k = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    head = 1, tail = 0;
    for (int i = 1; i <= n; i++) {
        while (head <= tail && a[que[tail]] > a[i]) tail--;
        que[++tail] = i;
        while (head <= tail && que[head] <= i - k) head++;
        if(i >= k) minx[i] = a[que[head]];
    }
    head = 1, tail = 0;
    for (int i = 1; i <= n; i++) {
        while (head <= tail && a[que[tail]] < a[i]) tail--;
        que[++tail] = i;
        while (head <= tail && que[head] <= i - k) head++;
        if(i >= k) maxx[i] = a[que[head]];
    }
    for (int i = k; i <= n; i++)
        printf("%d ", minx[i]);
    printf("\n");
    for (int i = k; i <= n; i++)
        printf("%d ", maxx[i]);
    printf("\n");
    return 0;
}