P1886 滑动窗口 /【模板】单调队列

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100010],l,r;
int f[100010][25],lg[100010];
int g[100010][25];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	lg[0]=-1;//lg[0]=-1,使lg[1]=0;
	for(int i=1;i<=n;i++){
		f[i][0]=a[i];//边界 
		g[i][0]=a[i];
		lg[i]=lg[i>>1]+1;//预处理logx 
	} 
	for(int j=1;j<=25;j++)//25=log100010 
		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]);
			g[i][j]=min(g[i][j-1],g[i+(1<<j-1)][j-1]);
		}
	for(int i=1;i+m-1<=n;i++){
		int l=i,r=i+m-1;
		int x=lg[r-l+1];
		cout<<min(g[l][x],g[r-(1<<x)+1][x])<<' ';
	}cout<<endl;
	for(int i=1;i+m-1<=n;i++){
		int l=i,r=i+m-1;
		int x=lg[r-l+1];
		cout<<max(f[l][x],f[r-(1<<x)+1][x])<<' ';
	}
	return 0;
}