#include<fstream>
int f[1000005],p[1000005],q[1000005],ans1[1000005],ans2[1000005],p1,p2,q1,q2,n,m,i;
using namespace std;

int main()
{
  ifstream cin("windows.in");
ofstream cout("std.out");

cin>>n>>m;
    for (i=0;i<n;i++)
        cin>>f[i];
    for (i=0;i<n;i++)
    {
		while (f[i]<=f[p[p2-1]]&&p2>p1) 
            p2--;
        p[p2++]=i;
		while (f[i]>=f[q[q2-1]]&&q2>q1)
            q2--;
        q[q2++]=i;
		if (i-p[p1]>=m)
            p1++;
		if (i-q[q1]>=m)
            q1++;
		if (i>=m-1)
        {
            ans1[i]=f[p[p1]];
            ans2[i]=f[q[q1]];
        }
	}
	cout<<ans1[m-1];
    for (i=m;i<n;i++) 
    cout<<' '<<ans1[i];
    printf("\n");
    cout<<ans2[m-1];
    for (i=m;i<n;i++) 
        cout<<' '<<ans2[i];
    printf("\n");
}






以上为5秒过的一个程序，也就是传说中的20行..。
然后我把它改成2分。。
#include<fstream>
using namespace std;
ifstream cin("windows.in");
ofstream cout("windows.out");
int minn[1000000+5],maxn[1000000+5],pmin1,pmin2,pmax1,pmax2,f[1000000+5],ansmin[1000000+5],ansmax[1000000+5],m,k;
int main()
{
    int i,r,l,mid;
    cin>>m>>k;
    for(i=0;i<m;++i)
    {
        cin>>f[i];
        r=pmin2;
        l=pmin1;
        while(l<r)
        {
            mid=l+r>>1;
            if(f[minn[mid]]>f[i])
                r=mid;
            else
                l=mid+1;
        }
        pmin2=r+1;
        minn[r]=i;
        r=pmax2;
        l=pmax1;
        while(l<r)
        {
            mid=l+r>>1;
            if(f[maxn[mid]]<f[i])
                r=mid;
            else
                l=mid+1;
        }
        pmax2=r+1;
        maxn[r]=i;
        if(i-minn[pmin1]>=k)
            ++pmin1;
        if(i-maxn[pmax1]>=k)
            ++pmax1;
        if(i>=k-1)
        {
            ansmin[i]=f[minn[pmin1]];
            ansmax[i]=f[maxn[pmax1]];
        }
    }
    for(i=k-1;i<m-1;++i)
        cout<<ansmin[i]<<" ";
    cout<<ansmin[m-1]<<"\n";
     for(i=k-1;i<m-1;++i)
        cout<<ansmax[i]<<" ";
    cout<<ansmax[m-1]<<"\n";
    return 0;
}





结果我传一次超时一次。已经传了2^N*NlogN*N*3次了。。&*(&*@$@)&$!)$&)(!@()*)!。。


求解释。