代码：
#include<stdio.h>
#include<set>
#include<math.h>
using namespace std;
int s[200005];
void build(int N,int n)
{
    int i,j,k;
    i=N;j=N+n-1;
    while(i>1)
    {
        for(k=i;k<j;k+=2)
            s[k>>1]=min(s[k],s[k+1]);
        if((j&1)==0)
            s[j>>1]=s[j];
        i>>=1;j>>=1;
    }
}
struct node
{
    int id,num;
};
struct cmp
{
    bool operator ()(node a,node b)
    {
        return a.num<b.num;
    }
};
int findx(int l,int r)
{
    int i,j,k;
    i=k=l;j=r;
    while(i<=j)
    {
        if(s[k]>s[i]) k=i;
        if(s[k]>s[j]) k=j;
        if((i&1)==1)  i++;
        if((j&1)==0)  j--;
        i>>=1;j>>=1;
    }
    while(k<l)
    {
        if(s[k]==s[(k<<1)+1]) k=(k<<1)+1;
        else
            k<<=1;

    }
    return k;
}
int main()
{
    int n,i,N,j;
    while(scanf("%d",&n)==1)
    {
        set<node,cmp>set1;
        set<node,cmp>::iterator it,it2;
        N=(int)pow(2.0,ceil(log2(n)));
        for(i=N;i<N+n;i++)
            scanf("%d",&s[i]);
        build(N,n);
        node temp,p;
        temp.id=N;temp.num=s[N];
        set1.insert(temp);
        int indx,ans=-1;
        for(i=N+1;i<N+n;i++)
        {
            p.id=i;p.num=s[i];
            it=set1.upper_bound(p);
            if(it==set1.end())
                j=N;
            else
                j=(*it).id+1;
            if(j<i)
            {
            indx=findx(j,i);
            if(i-indx!=0&&i-indx>ans)
                ans=i-indx;
            }
            set1.insert(p);
        }
        printf("%d\n",ans);
    }
    return 0;
}

• Re:谁能帮忙看下为什么Nlog（N）的时间会超时呢？ (13) snybzi 2010-07-22 13:19:25