#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+10;

int n,m,t;
int f[N][21],g[N][21];
int a[N];

inline void read(int &x)
{
	x = 0;int f = 1;char c = getchar();
	while(!isdigit(c)) {if(c == '-')f = -1;c = getchar();}
	while(isdigit(c)) {x = (x<<1)+(x<<3)+(c^48);c = getchar();}
}

void ST_init_f()
{
	for(int i=1;i<=n;i++) f[i][0] = a[i];
	int t = log(n)/log(2)+1;
	for(int j=1;j<t;j++)
		for(int i=1;i<=n-(1<<j)+1;i++)
			f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}

void ST_init_g()
{
	for(int i=1;i<=n;i++) g[i][0] = a[i];
	int t = log(n)/log(2)+1;
	for(int j=1;j<t;j++)
		for(int i=1;i<=n-(1<<j)+1;i++)
			g[i][j] = min(g[i][j-1],g[i+(1<<(j-1))][j-1]);
}

int query_f(int l,int r)
{
	int k = log(r-l+1)/log(2);
	return max(f[l][k],f[r-(1<<k)+1][k]);
}

int query_g(int l,int r)
{
	int k = log(r-l+1)/log(2);
	return min(g[l][k],g[r-(1<<k)+1][k]);
}

int main()
{
	read(n);read(m);
	for(int i=1;i<=n;i++) cin >> a[i];
	ST_init_f();
    ST_init_g();
	for(int i=1;i<=(n-m+1);i++)
        cout << query_f(i,i+m-1) << " " << query_g(i,i+m-1) << endl;
	return 0;
}

和上一题几乎一模一样，甚至工作量更小了一点，详见上题。

PS：这题似乎线段树和树状数组能过。

#include <bits/stdc++.h>
using namespace std;
const int LXB = 1e5+5;

int n,m;
int a[LXB],f[LXB][20],f1[LXB][20];

int rmq1(int l,int r)
{
    int k=0;
    while((1<<(k+1))<=(r-l+1))
        k++;
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int rmq2(int l,int r)
{
    int k=0;
    while((1<<(k+1))<=(r-l+1))
        k++;
    return min(f1[l][k],f1[r-(1<<k)+1][k]);
}


int main()
{
    scanf("%d%d", &n, &m);
    int x,y;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        f[i][0] = a[i];
        f1[i][0]=a[i];
    }
    
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i+(1<<j)-1<=n; i++)
            f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i+(1<<j)-1<=n; i++)
            f1[i][j] = min(f1[i][j-1],f1[i+(1<<(j-1))][j-1]);
            
    for(int i=1; i<=n-m+1; i++)
    {
        printf("%d ",rmq1(i,i+m-1));
        printf("%d\n",rmq2(i,i+m-1));
    }
    
    return 0;
}

下面是线段树解，慢了一倍...

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define Debug  cout<<1<<endl;
#define nel rt<<1
#define ner rt<<1|1

const int LXB=1e5+10;
const int INF=(1<<31)-1;

int n,m,k,l,ans;
int tree[LXB<<2],num[LXB],tr1[LXB<<2];

void pup(int rt){
    tree[rt]=max(tree[nel],max(tree[ner],tree[rt]));
}

void pup1(int rt){
    tr1[rt]=min(tr1[nel],min(tr1[ner],tr1[rt]));
}

void build(int l,int r,int rt){
    if(l==r){tree[rt]=num[l];return;}
    int m=(l+r)/2;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pup(rt);
}

void bu1(int l,int r,int rt){
    if(l==r){tr1[rt]=num[l];return;}
    int m=(l+r)/2;
    bu1(l,m,rt<<1);
    bu1(m+1,r,rt<<1|1);
    pup1(rt);
}

int out(int l1,int r1,int l,int r,int rt){
    if(l1<=l and r<=r1){
        return tree[rt];
    }
    int m=(l+r)/2;
    int ans=-INF;
    if(l1<=m)ans=max(out(l1,r1,l,m,rt<<1),ans);
    if(r1> m)ans=max(out(l1,r1,m+1,r,rt<<1|1),ans);
    return ans;
}

int out1(int l1,int r1,int l,int r,int rt){
    if(l1<=l and r<=r1){
        return tr1[rt];
    }
    int m=(l+r)/2;
    int ans=INF;
    if(l1<=m)ans=min(out1(l1,r1,l,m,rt<<1),ans);
    if(r1> m)ans=min(out1(l1,r1,m+1,r,rt<<1|1),ans);
    return ans;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    
    for(int i=1;i<=n;i++){
        cin>>num[i];
    }
    memset(tr1,0x3f,sizeof(tr1));
    fill(tree+1,tree+1+4*n,-INF);
    build(1,n,1);
    bu1(1,n,1);
    int x,y;
    
    for(int i=1;i<=n-m+1;i++){
        cout<<out(i,i+m-1,1,n,1)<<" "<<out1(i,i+m-1,1,n,1)<<endl;
    }
    return 0;
}