http://poj.org/problem?id=2823
单调队列：
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(" "); 44 printf("%d", ax[0]); 45 for(int i = 1; i < k1; i++) printf(" %d", ax[i]); 46 printf(" "); 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 }
堆维护：
（代码写得有些冗余了）
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int maxn = 1e6 + 10; 6 int n, k; 7 int a[maxn]; 8 int hx[maxn], idx[maxn], cidx[maxn]; 9 int hy[maxn], idy[maxn], cidy[maxn]; 10 int ax[maxn], ay[maxn], k1; 11 12 void swap(int &a, int &b) { int tem = b; b = a; a = tem; } 13 14 void adjx_down(int pos){ 15 int pi = pos << 1; 16 while(pi <= k){ 17 //until reach the boundary 18 if(pi < k && hx[pi + 1] > hx[pi]) ++pi; 19 //point to the larger subnode 20 if(hx[pi] <= hx[pi >> 1]) break; 21 //right place to insert 22 swap(hx[pi], hx[pi >> 1]); 23 swap(idx[cidx[pi]], idx[cidx[pi >> 1]]); 24 swap(cidx[pi], cidx[pi >> 1]); 25 //push up node pi(swap with fa(pi)) 26 pi <<= 1; 27 //continue comparsion 28 } 29 } 30 31 void adjy_down(int pos){ 32 int pi = pos << 1; 33 while(pi <= k){ 34 if(pi < k && hy[pi + 1] < hy[pi]) ++pi; 35 if(hy[pi] >= hy[pi >> 1]) break; 36 swap(hy[pi], hy[pi >> 1]); 37 swap(idy[cidy[pi]], idy[cidy[pi >> 1]]); 38 swap(cidy[pi], cidy[pi >> 1]); 39 pi <<= 1; 40 } 41 } 42 43 void adjx_up(int pos){ 44 int pi = pos; 45 while(pi != 1 && hx[pi >> 1] < hx[pi]){ 46 swap(hx[pi], hx[pi >> 1]); 47 swap(idx[cidx[pi]], idx[cidx[pi >> 1]]); 48 swap(cidx[pi], cidx[pi >> 1]); 49 pi >>= 1; 50 } 51 } 52 53 void adjy_up(int pos){ 54 int pi = pos; 55 while(pi != 1 && hy[pi >> 1] > hy[pi]){ 56 swap(hy[pi], hy[pi >> 1]); 57 swap(idy[cidy[pi]], idy[cidy[pi >> 1]]); 58 swap(cidy[pi], cidy[pi >> 1]); 59 pi >>= 1; 60 } 61 } 62 63 void init(){ 64 for(int i = 1; i <= k; i++) hy[i] = hx[i] = a[i], idy[i] = cidy[i] = idx[i] = cidx[i] = i; 65 //idx :: pos in current array -> pos in hx 66 //cidx :: pos in hx -> pos in the current array 67 for(int i = k >> 1; i >= 1; i--) adjx_down(i), adjy_down(i); 68 } 69 70 void insertx(int num, int p, int pos){ 71 cidx[pos] = p; 72 idx[p] = pos; 73 hx[pos] = num; 74 if(pos != 1 && num > hx[pos >> 1]) adjx_up(pos); 75 else adjx_down(pos); 76 } 77 78 void inserty(int num, int p, int pos){ 79 cidy[pos] = p; 80 idy[p] = pos; 81 hy[pos] = num; 82 if(pos != 1 && num < hy[pos >> 1]) adjy_up(pos); 83 else adjy_down(pos); 84 } 85 86 void solve(){ 87 //the problem is how to delete the oldest element 88 //easy to init and insert 89 init(); 90 k1 = 0; 91 ay[k1] = hy[1]; 92 ax[k1++] = hx[1]; 93 for(int i = k + 1; i <= n; i++){ 94 inserty(a[i], i, idy[i - k]); 95 insertx(a[i], i, idx[i - k]); 96 ay[k1] = hy[1]; 97 ax[k1++] = hx[1]; 98 } 99 for(int i = 0; i < k1 - 1; i++) printf("%d ", ay[i]); 100 printf("%d ", ay[k1 - 1]); 101 for(int i = 0; i < k1 - 1; i++) printf("%d ", ax[i]); 102 printf("%d ", ax[k1 - 1]); 103 } 104 105 int main(){ 106 //freopen("in.txt", "r", stdin); 107 while(~scanf("%d%d", &n, &k)){ 108 for(int i = 1; i <= n; i++) scanf("%d", &a[i]); 109 solve(); 110 } 111 return 0; 112 }