题目链接：

用RMQ超时了，我想应该是不会的，看discuss说，之前RMQ过了。

维护两个单调队列。

单调递减的队列，每插入一个时：

超过单调队列长度，左移头指针。

第一个或者符合条件，直接加到后面。

否则，一直退；

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5  6 using namespace std; 7  8 const int N = 1000000 + 5; 9 10 int n,m;11 int a[N],q[N];12 13 void MinQ()14 {15     int h=1,t=0;16     q[1] = 1;17     for(int i=1;i<=n;i++) {18         if(i-q[h]==m) h++;19 20         if(t==h-1||a[i]>a[q[t]]) {21             t++;22             q[t] = i;23         }24         else {25             while(t>=h&&a[i]<=a[q[t]])26             {27                 q[t] = i;28                 t--;29             }30             t++;31         }32         if(i>=m) printf("%d ",a[q[h]]);33 34     }35     puts("");36 }37 38 void MaxQ()39 {40     int h=1,t=0;41     q[1] = 1;42     for(int i=1;i<=n;i++) {43 44         if(i-q[h]==m) h++;45 46         if(t==h-1||a[i]
         
          =h&&a[i]>=a[q[t]])52             {53                 q[t] = i;54                 t--;55             }56             t++;57 58         }59         if(i>=m) printf("%d ",a[q[h]]);60 61     }62 }63 64 int main()65 {66     cin>>n>>m;67     for(int i=1;i<=n;i++) {68         scanf("%d",&a[i]);69     }70 71     MinQ();72     MaxQ();73 74     return 0;75 }
         
        
       
      
     

题目链接：

和单调递增队列一样。

1 /* 2 RunID: 727738 3 UserID: TreeDream 4 Submit time: 2017-02-16 00:04:08 5 Language: C++ 6 Length: 1167 Bytes. 7 Result: Accepted 8 */ 9 10 //#include 
     
      11 #include 
      
       12 #include 
       
        13 #include 
        
         14 #include 
         
          15 16 17 using namespace std;18 19 const int maxn = 1000000 + 5;20 int a[maxn];21 int q[maxn];22 23 int main()24 {25     //freopen("in.txt","r",stdin);26     int t;27     scanf("%d",&t);28 29     while(t--)30     {31         char op[10];32         scanf("%s",op);33 34         int head = 1,tail = 0;35 36         q[0] = -1;37 38         int i=0,j=1;39         char cmd[10],name[10];40         int len = 0;41 42         while(scanf("%s",cmd))43         {44             if(strcmp(cmd,"END")==0) break;45 46             if(cmd[0]=='C')     //插入是有条件的47             {48                 scanf("%s",name);49                 len ++;50                 scanf("%d",&a[len]);51                 while(head<=tail&&a[q[tail]]<=a[len])52                     tail--;53                 q[++tail] = len;54             }55 56             else if(cmd[0]=='G')57             {58                 while(head<=tail&&q[head]<=j)59                     head++;60                 j++;61             }62             else printf("%d\n",head>tail?-1:a[q[head]]);63         }64     }65 66     return 0;67 }
         
        
       
      
     

 

 

参考：