洛谷 P1886 滑动窗口
题目描述
现在有一堆数字共N个数字（N<=10^6），以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如：
The array is [1 3 -1 -3 5 3 6 7], and k = 3.
输入格式
输入一共有两行，第一行为n,k。
第二行为n个数(<INT_MAX).
输出格式
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入输出样例
输入 #1复制
输出 #1复制
说明/提示
50%的数据，n<=10^5
100%的数据，n<=10^6
题解：
多种数据结构练习的模板题。滑动的过程模拟一下即可。
这里我先贴一份初次AC的线段树代码，其他的数据结构可能以后会慢慢更新，欢迎大家在评论区催我。
代码：（线段树）
#include<cstdio>
#include<algorithm>
#define lson pos<<1
#define rson pos<<1|1
using namespace std;
const int maxn=1e6+1;
const int INF=2147483647;
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read()
{
int x=0,f=1;
char ch=nc();
while(ch<'0'){if(ch=='-')f=-1;ch=nc();}
while(ch>='0') x=x*10+ch-'0',ch=nc();
return x*f;
}
int n,k;
int a[maxn];
int tree[maxn<<2],seg[maxn<<2];
void build(int pos,int l,int r)
{
int mid=(l+r)>>1;
if(l==r)
{
tree[pos]=a[l];
seg[pos]=a[l];
return;
}
build(lson,l,mid);
build(rson,mid+1,r);
tree[pos]=max(tree[lson],tree[rson]);
seg[pos]=min(seg[lson],seg[rson]);
}
int query(int pos,int l,int r,int x,int y)
{
int ret=-INF;
int mid=(l+r)>>1;
if(x<=l && r<=y)
return tree[pos];
if(x<=mid)
ret=max(ret,query(lson,l,mid,x,y));
if(y>mid)
ret=max(ret,query(rson,mid+1,r,x,y));
return ret;
}
int ask(int pos,int l,int r,int x,int y)
{
int ret=INF;
int mid=(l+r)>>1;
if(x<=l && r<=y)
return seg[pos];
if(x<=mid)
ret=min(ret,ask(lson,l,mid,x,y));
if(y>mid)
ret=min(ret,ask(rson,mid+1,r,x,y));
return ret;
}
int main()
{
n=read();k=read();
for(int i=1;i<=n;i++)
a[i]=read();
build(1,1,n);
for(int i=1;i<=n-k+1;i++)
printf("%d ",ask(1,1,n,i,i+k-1));
puts("");
for(int i=1;i<=n-k+1;i++)
printf("%d ",query(1,1,n,i,i+k-1));
return 0;
}