记录编号	523077	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	1.460 s
提交时间	2018-11-17 20:02:55	内存使用	83.27 MiB

#include<bits/stdc++.h>
using namespace std;
int m,n,k,l,o;
int a[1000010];
int d1[1000010][10];
int d2[1000010][10]; 
void add_init(int n)
{ for (int i=1;i<=n;i++)
  d2[i][0]=a[i];
  for(int j=1;(1<<j)<=n;j++)
   for (int i=1;i+(1<<j)-1<=n;i++)
  d2[i][j]=max(d2[i][j-1],d2[i+(1<<(j-1))][j-1]);
}
void add_innit(int n)
{ for (int i=1;i<=n;i++)
  d1[i][0]=a[i];
  for(int j=1;(1<<j)<=n;j++)
   for (int i=1;i+(1<<j)-1<=n;i++)
  d1[i][j]=min(d1[i][j-1],d1[i+(1<<(j-1))][j-1]);
}
int RMQ(int r,int l)
{ int k=0;
  while ((1<<(k+1))<=l-r+1) k++;
  return max(d2[r][k],d2[l-(1<<k)+1][k]);
}
int RMQ2(int r,int l)
{int k=0;
  while ((1<<(k+1))<=l-r+1) k++;
  return min(d1[r][k],d1[l-(1<<k)+1][k]);
}
int main()
{ freopen("window.in","r",stdin);
  freopen("window.out","w",stdout);
  scanf("%d%d",&m,&l);
  for (int i=1;i<=m;i++)
  scanf("%d",&a[i]);
  add_init(m);
  add_innit(m);
  for (int i=l;i<=m;i++)
  printf("%d ",RMQ2(i-l+1,i));
  printf("\n");
  for (int i=l;i<=m;i++)
  { printf("%d ",RMQ(i-l+1,i));
  }
  return 0;
}