poj2823 Sliding Window

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int maxn = 1e6 + 10;
 6 int a[maxn];
 7 int n, k;
 8 int mqx[maxn], idx[maxn], frontx, rearx;//monotone queue
 9 int mqy[maxn], idy[maxn], fronty, reary;
10 int ax[maxn], ay[maxn], k1;
11 
12 void solve(){
13     frontx = fronty = 0;
14     rearx = reary = 0;
15     //head closed & tail open interval
16     for(int i = 1; i <= k; i++){
17         while(rearx > frontx && mqx[rearx - 1] <= a[i]) --rearx;
18         mqx[rearx++] = a[i];
19         idx[rearx - 1] = i;
20         while(reary > fronty && mqy[reary - 1] >= a[i]) --reary;
21         mqy[reary++] = a[i];
22         idy[reary - 1]  = i;
23     }
24     k1 = 0;
25     ax[k1] = mqx[frontx], ay[k1++] = mqy[fronty];
26     for(int i = k + 1; i <= n; i++){
27         int tail = i - k + 1;
28         while(rearx  > frontx && mqx[rearx - 1] <= a[i]) --rearx;
29         mqx[rearx++] = a[i];
30         idx[rearx - 1] = i;
31         while(idx[frontx] < tail){
32             ++frontx;
33         }
34         while(reary > fronty && mqy[reary - 1] >= a[i]) --reary;
35         mqy[reary++] = a[i];
36         idy[reary - 1] = i;
37         while(idy[fronty] < tail) ++fronty;
38         ax[k1] = mqx[frontx];
39         ay[k1++] = mqy[fronty];
40     }
41     printf("%d", ay[0]);
42     for(int i = 1; i < k1; i++) printf(" %d", ay[i]);
43     printf("\n");
44     printf("%d", ax[0]);
45     for(int i = 1; i < k1; i++) printf(" %d", ax[i]);
46     printf("\n");
47 }
48 
49 int main(){
50     //freopen("in.txt", "r", stdin);
51     while(~scanf("%d%d", &n, &k)){
52         for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
53         solve();
54     }
55     return 0;
56 }