描述
Wind 设计了很多机器人。但是它们都认为自己是最强的，于是，一场比赛开始了……
机器人们都想知道谁是最敏捷的，于是它们进行了如下一个比赛。首先，他们面前会有一排共 n 个数，它们比赛看谁能最先把每连续 k 个数中最大和最小值写下来，当然，这些机器人运算速度都很快，它们比赛的是谁写得快。
但是 Wind 也想知道答案，你能帮助他吗？
输入
第一行为 n,k(1≤k≤n≤105)，意义如题目描述。
第二行共 n 个数，为数字序列，所有数字均在 int 范围内，即所有数均为整数，且在 [−231,231−1]范围内。
输出
共 n−k+1 行，第 i 行为第 i 至第 i+k−1 这 k 个数中的最大和最小值。
样例输入
5 3
1 2 3 4 5
样例输出
3 1
4 2
5 3
思路：根据板子我们用f(i,j)表示i到j区间的最大值，z(i,j)表示i到j区间的最小值
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5+10,inf = 0x3f3f3f3f,lgn = 20; int lg[N],f[N][lgn+5],z[N][lgn+5],a[N]; int n,k,x,y; void rmq() { lg[0] = -1; for(int i=1;i<=n;i++) f[i][0] = z[i][0] = a[i],lg[i] = lg[i>>1]+1; //预处理出长度为1-n的lg值 for(int j=1;j<=lgn;j++) //计算f[i][j] for(int i=1;i+(1<<j)-1<=n;i++) //区间边界不超过n f[i][j] = max(f[i][j-1],f[i+(1<<j-1)][j-1]),z[i][j] = min(z[i][j-1],z[i+(1<<j-1)][j-1]); } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); rmq(); //预处理rmq n = n-k+1; int x,y,s; for(int i=1;i<=n;i++) { x = i,y = i+k-1; s = lg[y-x+1]; printf("%d %d\n",max(f[x][s],f[y-(1<<s)+1][s]),min(z[x][s],z[y-(1<<s)+1][s])); } return 0; }