POJ 2452 Sticks Problem ★ (单调栈+RMQ)

题目大意：给出一串数，找到最长的一个连续子区间，使得区间的头元素为区间内最小值，末元素为区间内最大值。长度L<=50000 挺好的一道题，自己没想出来T T……看题解才受到了启发…… 用单调栈，预处理所有点的一个right[i]，表示i点向后扩展到的最远的以height[i]为最小值的区间。然后用RMQ求每个区间的最大值的位置。(这里我用的线段树实现的……不会ST，神牛鄙视我吧……) 于是我们先用单调栈求出right[i]数组，然后对于i~right[i]的区间，求出最大值所在位置p,i~p就为i向后能扩展到的最远的一个区间。对于每个点都向后查询一次，就能求出最优解。复杂度O(NlgN)。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MID(x,y) ((x+y)>>1)
using namespace std;
typedef long long LL;

int height[50005], right[50005];
int maxn[200005];
void pushup(int rt){
    maxn[rt] = max(maxn[rt<<1], maxn[rt<<1|1]);
    return ;
}
void debug_tree(int l, int r, int rt){
    if (l == r){
        printf("%d %d %d\n", rt, l, maxn[rt]);
        return ;
    }
    int mid = MID(l, r);
    debug_tree(l, mid, rt<<1);
    debug_tree(mid+1, r, rt<<1|1);
    return ;
}
void build_tree(int l, int r, int rt){
    if (l == r){
        maxn[rt] = height[l];
        return ;
    }
    int mid = MID(l, r);
    build_tree(l, mid, rt<<1);
    build_tree(mid+1, r, rt<<1|1);
    pushup(rt);
    return ;
}
int query_max(int s, int t, int l, int r, int rt){
    if (s <= l && r <= t){
        return maxn[rt];
    }
    int mid = MID(l,r);
    int ans = 0;
    if (s <= mid)   ans = max(ans, query_max(s, t, l, mid, rt<<1));
    if (mid < t)    ans = max(ans, query_max(s, t, mid+1, r, rt<<1|1));
    return ans;
}
int query_position(int s, int t, int l, int r, int rt){
    if (l == r){
        return l;
    }
    int mid = MID(l,r);
    int max1 = 0, max2 = 0;
    if (s <= mid)   max1 = query_max(s, t, l, mid, rt<<1);
    if (mid < t)    max2 = query_max(s, t, mid+1, r, rt<<1|1);
    if (max1 > max2)
        return query_position(s, t, l, mid, rt<<1);
    else
        return query_position(s, t, mid+1, r, rt<<1|1);
}
stack  S;
int main(){
    int n;
    while(scanf("%d", &n) == 1){
        for (int i = 1; i <= n; i ++)
            scanf("%d", &height[i]);
        build_tree(1, n, 1);
        //debug_tree(1, n, 1);
        while(!S.empty())
            S.pop();
        height[n+1] = -1;
        for (int i = 1; i <= n + 1; i ++){
            if (S.empty() || height[S.top()] < height[i]){
                S.push(i);
            }
            else{
                while(!S.empty() &&height[S.top()] >= height[i]){
                    right[S.top()] = i;
                    S.pop();
                }
                S.push(i);
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i ++){
            //printf("%d %d\n", i, right[i]);
            res = max(res, query_position(i, right[i]-1, 1, n, 1) - i );
        }
        if (res == 0)
            printf("-1\n");
        else    printf("%d\n", res);
    }
	return 0;
}

举杯独醉，饮罢飞雪，茫然又一年岁。 ------AbandonZHANG