#include <stdio.h>

#define MAXVALUE 1000000

typedef struct{
    int min, max;
}TREE;
TREE tree[1000000];

int A[50010];

int min(int a, int b) {return ((a < b) ? a : b);}
int max(int a, int b) {return ((a > b) ? a : b);}

/*
    [l, r] : 当前结点代表的区域
    node   : 当前结点编号 
    建树复杂度为O(N) 
    初始调用Build_Tree(1, N, 1);
*/
void Build_Tree(int l, int r, int node){
    if(l == r) {
        tree[node].min = A[l];
        tree[node].max = -1;
        return;
    }
    
    int k = (l + r) / 2;
    Build_Tree(l, k, node*2);
    Build_Tree(k + 1, r, node*2+1);
    tree[node].min = min (tree[node*2].min, tree[node*2+1].min);
    tree[node].max = max (tree[node*2].max, tree[node*2+1].max);
    return;
}


int GetMin(int l, int r, int value, int node){
    if(node == 1 && tree[node].min > value) return -1;
    else if(l == r){
        if(tree[node].min < value) return l;
        else return -1;
    }
    else{
        if(tree[node*2].min < value) return GetMin(l, (l+r)/2, value, node*2);
        else return GetMin((l+r)/2+1, r, value, node*2+1);
    }
    
}

int GetMax(int l, int r, int i, int j, int node){
    if(l == r) return l;
    int k = (l + r) / 2;
    if(j <= k) return GetMax(l, k, i, j, node*2);
    else if(i > k) return GetMax(k+1, r, i, j, node*2+1);
    else if(tree[node*2].max >= tree[node*2+1].max) {
        if(j <= k)
            return GetMax(l, k, i, j, node*2);
        else return GetMax(l, k, i, k, node*2);
    }
    else{
        if(i > k)
            return GetMax(k+1, r, i, j, node*2+1);
        else return GetMax(k+1, r, k+1, j, node*2+1);
    }
}

void Insert(int l, int r, int k, int value, int node){
    if(l == r){
        tree[node].max = value;
        tree[node].min = value;
        return;
    }
    
    if(k > (l + r) / 2 ) Insert((l + r) / 2 + 1, r, k, value, node*2+1);
    else Insert(l, (l+r)/2, k, value, node*2);
    tree[node].min = min (tree[node*2].min, tree[node*2+1].min);
    tree[node].max = max (tree[node*2].max, tree[node*2+1].max);
    return;
}

int main()
{
    int i, n, fir, Min, ans, sec, ANS;
    while(scanf("%d", &n) != EOF){
        for(i = 1; i <= n; i++) 
            A[i] = MAXVALUE;
        ANS = -1;
        Build_Tree(1, n, 1);
        for(i = 1; i <= n; i++) scanf("%d", A+i);
        for(i = n; i >= 1; i--){
            fir = i;
            Min = GetMin(1, n, A[i], 1);
            if(Min == -1) sec = n;
            else sec = Min-1;
            ans = GetMax(1, n, fir, sec, 1) - fir;
            //printf("i = %d, A[i] = %d, Min = %d, fir = %d, sec = %d, ans = %d\n", i, A[i], Min, fir, sec, ans);
            if(ans > ANS) ANS = ans;
            
            Insert(1, n, i, A[i], 1);
        }
        if(ANS > 0) printf("%d\n", ANS);
        else printf("-1\n");
    }
    return 0;
}

• 看这个，加了注释的。WA (2800) busycai 2008-06-20 11:37:07