1 //6000ms 1Y 单调队列 需要维护两个单调队列 每一个需要维护它们的开始和结束元素的位置,用一个万能元素当第一个元素,当比较到它时必将  2 //被替换,每一个单调队列中的元素都记录一个作用时间域. 每个元素进队一次出队一次 所以O(n)  3 #include <iostream>  4 #include <cstdio>  5 #include <string.h>  6 #include <stdlib.h>  7 #include <math.h>  8 #include <vector>  9 #include <algorithm> 10 struct node{ 11    int time,v; 12 }; 13 using namespace std; 14 #define maxn 1000005 15 #define INF 0x7fffffff 16 node maxque[maxn],minque[maxn]; 17 int minquelen,maxquelen,minquestart,maxquestart,i,j; 18 int printmin[maxn],printmax[maxn]; 19 void insertmax(int v) 20 { 21     int q; 22     for(q=maxquelen;q>=0;q--) 23      if(maxque[q].v>v) {maxquelen=q+1;maxque[maxquelen].v=v;maxque[maxquelen].time=j;break;} 24 } 25 void insertmin(int v) 26 { 27     int q; 28     for(q=minquelen;q>=0;q--) 29      if(minque[q].v<v) {minquelen=q+1;minque[minquelen].v=v;minque[minquelen].time=j;break;} 30 } 31 int querymax() 32 { 33     if(i<maxque[maxquestart+1].time) 34      return maxque[maxquestart+1].v; 35     else 36      if(i==maxque[maxquestart+1].time) 37      { 38        int temp=maxque[maxquestart+1].v; 39        maxque[++maxquestart]=maxque[0]; 40        return temp; 41      } 42      else 43      { 44          maxque[++maxquestart]=maxque[0]; 45          return querymax(); 46      } 47 } 48 int querymin() 49 { 50     if(i<minque[minquestart+1].time) 51      return minque[minquestart+1].v; 52     else 53      if(i==minque[minquestart+1].time) 54      { 55        int temp=minque[minquestart+1].v; 56        minque[++minquestart]=minque[0]; 57        return temp; 58      } 59      else 60      { 61         minque[++minquestart]=minque[0]; 62         return querymin(); 63      } 64 } 65 int main() 66 { 67     //freopen("in.txt","r",stdin); 68     int n,k; 69     while(~scanf("%d%d",&n,&k)) 70     { 71         int x; 72         if(k>n) k=n; 73         maxque[0].v=INF;minque[0].v=-INF; 74         minquelen=maxquelen=minquestart=maxquestart=0; 75         for(i=1;i<k;i++) 76         { 77          j=i; 78          scanf("%d",&x); 79          insertmax(x); 80          insertmin(x); 81          //cout<<"i="<<i<<" x="<<x<<endl; 82         } 83         /*cout<<"minquestart="<<minquestart<<endl; 84         for(int t=1;t<=minquelen;t++) 85          cout<<"minque["<<t<<"].v="<<minque[t].v<<" minque["<<t<<"].time="<<minque[t].time<<endl; 86         cout<<"maxquestart="<<maxquestart<<endl; 87         for(int t=1;t<=maxquelen;t++) 88          cout<<"maxque["<<t<<"].v="<<maxque[t].v<<" maxque["<<t<<"].time="<<maxque[t].time<<endl; 89         */ 90         //cout<<"adsf"<<endl; 91         for(i=1;i<=n-k+1;i++) //n-k 92         { 93           //cout<<"adsf"<<endl; 94           j=i+k-1; 95           scanf("%d",&x); 96           insertmax(x); 97           insertmin(x); 98           printmax[i]=querymax(); 99           printmin[i]=querymin();100           //cout<<"1"<<endl;101           //cout<<"querymax()="<<printmax[i]<<endl;102           //cout<<"querymin()="<<printmin[i]<<endl;103         }104         for(i=1;i<=n-k+1;i++)105         {106          if(i!=1) printf(" ");107          printf("%d",printmin[i]);108         }109         printf("\n");110         for(i=1;i<=n-k+1;i++)111         {112          if(i!=1) printf(" ");113          printf("%d",printmax[i]);114         }115         printf("\n");116     }117     return 0;118 }