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

最近在练线段树

样例只对了最大值的那一行

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000005];
struct node
{
	int maxx,l,r,minn;
}tree[4000005];
void build(int k,int ll,int rr)
{
	tree[k].l=ll;
	tree[k].r=rr;
	if(ll==rr){
		tree[k].maxx=a[ll];
		tree[k].minn=a[ll];
		return;
	}
	int mid=(ll+rr)>>1;
	build(k*2,ll,mid);
	build(k*2+1,mid+1,rr);
	tree[k].maxx=max(tree[k*2].maxx,tree[k*2+1].maxx);
	tree[k].minn=min(tree[k*2].minn,tree[k*2+1].minn);
	return;
}
int ask(int k,int ll,int rr,int x,int y)//大的 
{
	if(x<=ll && rr<=y) return tree[k].maxx;
	int mid=(ll+rr)>>1;
	int ans=-1;
	if(x<=mid) ans=max(ans,ask(k*2,ll,mid,x,y));
	if(y>mid) ans=max(ans,ask(k*2+1,mid+1,rr,x,y));
	return ans;
}
int ask1(int k,int ll,int rr,int x,int y)//小的 
{
	if(x<=ll && rr<=y) return tree[k].minn;
	int mid=(ll+rr)>>1;
	int ans=999999999999;
	if(x<=mid) ans=min(ans,ask(k*2,ll,mid,x,y));
	if(y>mid) ans=min(ans,ask(k*2+1,mid+1,rr,x,y));
	return ans;
}
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	build(1,1,n);
	for(int i=1;i<=n-m+1;i++){
		printf("%lld ",ask1(1,1,n,i,i+m-1));
	}
	printf("\n");
	for(int i=1;i<=n-m+1;i++){
		printf("%lld ",ask(1,1,n,i,i+m-1));
	}
	
	return 0;
}