我们可以用线段树来维护区间的最大最小值，由于分开求会tle，所以我们要同时查询 线段树还是太慢了qwq code：
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <queue> #include <cctype> #include <stack> #include <cmath> #include <ctime> using namespace std; #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r const int maxn=1e7; int a[maxn],i,n,k; struct min_max{ int minx,maxx; }num;// 结构体，存储最大最小值 inline void read(int &x){// 快读 char c; int f=1; while(!isdigit(c=getchar())) if(c=='-') f=-1; x=c-'0'; while(isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0'; x*=f; } struct SegmentTree{// Segment Tree const int inf=1<<30; int minv[maxn],maxv[maxn]; inline void pushup(int rt) { maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]); minv[rt]=min(minv[rt<<1],minv[rt<<1|1]); } inline void BuildTree(int rt, int l, int r){ if(l==r) { minv[rt]=maxv[rt]=a[l]; return; } int mid=(l+r)>>1; BuildTree(lson); BuildTree(rson); pushup(rt); } inline min_max query_min(int rt, int l, int r, int ql, int qr){ if(ql<=l&&qr>=r) return (min_max){minv[rt],maxv[rt]}; int mini=inf,maxi=-inf; int mid=(l+r)>>1; min_max t; if(ql<=mid){ t=query_min(lson,ql,qr); mini=min(mini,t.minx); maxi=max(maxi,t.maxx); } if(qr>mid){ t=query_min(rson,ql,qr); mini=min(mini,t.minx); maxi=max(maxi,t.maxx); } return (min_max){mini,maxi}; } }seg; signed main() { read(n); read(k); for(i=1;i<=n;i++) { read(a[i]); } seg.BuildTree(1,1,n); for(i=1;i<=n-k+1;i++) { num=seg.query_min(1,1,n,i,i+k-1); printf("%d ",num.minx); a[i]=num.maxx; } puts(""); for(i=1;i<=n-k+1;i++) printf("%d ",a[i]); return 0; }