模板题
以后再写 = =
还需要二分优化 (减少常数?)
- #include<iostream>
- #include<cstdio>
- using namespace std;
- #define REP(r,x,y) for(register int r=(x); r<(y); r++)
- #define REPE(r,x,y) for(register int r=(x); r<=(y); r++)
- #ifdef sahdsg
- #define DBG(...) printf(__VA_ARGS__)
- #else
- #define DBG(...)
- #endif
- #define MAXN 1000007
- int arr[MAXN], que[MAXN], l, r;
- int n,k;
- int main() {
- #ifdef sahdsg
- freopen("in.txt", "r", stdin);
- #endif
- scanf("%d%d", &n, &k);
- REP(i,0,n) {
- scanf("%d", &arr[i]);
- }
- l=0, r=0;
- REP(i,0,k-1) {
- while(l<r && arr[que[r-1]]>arr[i]) r--;
- que[r++] = i;
- }
- bool fi = false;
- REP(i,k-1,n) {
- if(que[l]<=i-k) l++;
- while(l<r && arr[que[r-1]]>arr[i]) r--;
- que[r] = i;
- if(fi) putchar(' '); else fi = true;
- printf("%d", arr[que[l]]);
- r++;
- }
- putchar('\n');
- fi = false;
- l=0, r=0;
- REP(i,0,k-1) {
- while(l<r && arr[que[r-1]]<arr[i]) r--;
- que[r++] = i;
- }
- REP(i,k-1,n) {
- if(que[l]<=i-k) l++;
- while(l<r && arr[que[r-1]]<arr[i]) r--;
- que[r] = i;
- if(fi) putchar(' '); else fi = true;
- printf("%d", arr[que[l]]);
- r++;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2977463.html