为什么会wa一个点,求dalao指点

P1886 滑动窗口 /【模板】单调队列

zirrtu @ 2017-01-22 11:16:07

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 1010000+5
#define INF 2147483647
using namespace std;
int a[MAXN],q[MAXN],p[MAXN],cnt,l=0,r=1,CNT,cnt2,CNT2,l2=0,r2=1,p2[MAXN],q2[MAXN],n,k;
void add(int x)
  {
       q[++r]=x;p[r]=++cnt;
       while(l<r&&q[r-1]>=q[r])
         {
            r--;
          q[r]=x;    
          p[r]=cnt;
       }
  }
void add2(int x)
  {
       q2[++r2]=x;p2[r2]=++cnt2;
       while(l2<r2&&q2[r2-1]<=q2[r2])
         {
            r2--;
          q2[r2]=x;    
          p2[r2]=cnt2;
       }
  }
void del()
  {
       CNT++;
       if(p[l]==CNT)l++;
  }
void del2()
  {
       CNT2++;
       if(p2[l2]==CNT2)l2++;
  }
int qu()
{
    return q[l];
}
int qu2()
{return q2[l2];}
int main()
  {
       int i,j,k,aa;
       for(i=1;i<=MAXN;i++)q[i]=INF;
       for(i=1;i<=MAXN;i++)q2[i]=-INF;
       scanf("%d%d",&n,&k);
       for(i=1;i<=n;i++)
         scanf("%d",&a[i]);
       for(i=1;i<=k;i++)
         add(a[i]);cout<<qu()<<" ";
       for(i=k+1;i<=n;i++)
         {
               add(a[i]);
               del();
          cout<<qu()<<" ";
       }
     cout<<endl;
     for(i=1;i<=k;i++)
         add2(a[i]);cout<<qu2()<<" ";
       for(i=k+1;i<=n;i++)
         {
               add2(a[i]);
               del2();
               cout<<qu2()<<" ";
       }
       return 0;
}

|