Palpitation_ @ 2019-07-29 12:59:00
RT,ST表,样例全输出0
#include<bits/stdc++.h>
using namespace std;
int a[100005],n,m,p[20][100005];int t=log2(n);int q[20][100005];
int querymax(int l,int r){
int t=log2(r-l+1);
return max(q[t][l],q[t][r-(1<<t)+1]);
}
void mmax(){
for(int k=1;k<=t;k++){
for(int i=1;i+(1<<k)-1<=n;i++){
q[k][i]=max(q[k-1][i],q[k-1][i+(1<<(k-1))]);
}
}
}
int querymin(int l,int r){
int t=log2(r-l+1);
return min(p[t][l],p[t][r-(1<<t)+1]);
}
void mmin(){
for(int k=1;k<=t;k++){
for(int i=1;i+(1<<k)-1<=n;i++){
p[k][i]=min(p[k-1][i],p[k-1][i+(1<<(k-1))]);
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&p[0][i]);
q[0][i]=p[0][i];
}
int l=1,r=m;
mmin();
for(int i=1;i<=n-m;i++){
printf("%d ",querymin(l,r));
l++,r++;
}
printf("\n");
mmax();
l=1,r=m;
for(int i=1;i<=n-m;i++){
printf("%d ",querymax(l,r));
l++,r++;
}
return 0;
}
by Palpitation_ @ 2019-07-29 13:12:13
个人觉得没问题啊啊啊
by ZYF_B @ 2019-07-29 13:14:33
为什么你的t在n读入前就算了
by Palpitation_ @ 2019-07-29 13:17:13
@ZYF_B sb了QAQ
by Palpitation_ @ 2019-07-29 13:22:07
@ZYF_B 可还是有点WA了啊https://www.luogu.org/record/21753556
by ZYF_B @ 2019-07-29 14:07:50
N<=1e6...
by Palpitation_ @ 2019-08-18 20:05:54
@ZYF_B 同学ST表A了啊