[已注销]!A8&kFzt @ 2019-08-26 20:04:03
评测结果
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000001];
int maxn[1000001][21],minn[1000001][21];
int rmqmin(int l,int r){
int k=log2(r-l+1);
return min(minn[l][k],minn[r-(1<<k)+1][k]);
}
int rmqmax(int l,int r){
int k=log2(r-l+1);
return max(maxn[l][k],maxn[r-(1<<k)+1][k]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) minn[i][0]=maxn[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
minn[i][j]=min(minn[i][j-1],minn[i+(1<<j-1)][j-1]);
maxn[i][j]=max(maxn[i][j-1],maxn[i+(1<<j-1)][j-1]);
}
}
for(int i=1;i<=n-m+1;i++){
int l=i,r=l+m-1,d,p;
d=rmqmin(l,r);
printf("%d ",d);
}
printf("\n");
for(int i=1;i<=n-m+1;i++){
int l=i,r=l+m-1,d,p;
d=rmqmax(l,r);
printf("%d ",d);
}
return 0;
}
by ⚡小林孑⚡ @ 2019-08-26 21:11:40
@光随影走
开了完隐,发一下代码
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n_,n=1,k,l,r,cnt;
const int INF=2147483647;
int dat[4000005],tree[4000005],dat2[4000005];
inline int min(int a,int b){
return a<b?a:b;
}
void init(){
while(n<n_) n*=2;
memset(dat,127/3,sizeof(dat));
memset(dat2,127/3,sizeof(dat2));
}
void build(int now,int l,int r){
if(l==r){
cnt++;
dat[now]=tree[cnt];
}
else{
int mid=(l+r)/2;
build(now*2,l,mid);
build(now*2+1,mid+1,r);
dat[now]=min(dat[now*2],dat[now*2+1]);
}
}
void build2(int now,int l,int r){
if(l==r){
cnt++;
dat2[now]=tree[cnt];
}
else{
int mid=(l+r)/2;
build2(now*2,l,mid);
build2(now*2+1,mid+1,r);
dat2[now]=max(dat2[now*2],dat2[now*2+1]);
}
}
int query(int a,int b,int k,int l,int r){
if(a>r||b<l) return INF;
if(l>=a&&b>=r) return dat[k];
else{
int mid=(l+r)/2;
int ls=query(a,b,k*2,l,mid);
int rs=query(a,b,k*2+1,mid+1,r);
return min(ls,rs);
}
}
int query2(int a,int b,int k,int l,int r){
if(a>r||b<l) return -INF;
if(l>=a&&b>=r) return dat2[k];
else{
int mid=(l+r)/2;
int ls=query2(a,b,k*2,l,mid);
int rs=query2(a,b,k*2+1,mid+1,r);
return max(ls,rs);
}
}
int main(){
cin>>n_>>k;
init();
for(int i=1;i<=n_;i++)
cin>>tree[i];
build(1,1,n);
cnt=0;
build2(1,1,n);
for(int i=1;i<=n_-k+1;i++)
printf("%d ",query(i,i+k-1,1,1,n));
putchar('\n');
for(int i=1;i<=n_-k+1;i++)
printf("%d ",query2(i,i+k-1,1,1,n));
}
by 梧桐灯 @ 2019-08-26 21:12:22
@脱发自动机 emmm这明明是线段树
by ⚡小林孑⚡ @ 2019-08-26 21:14:40
@光随影走 基于线段树的RMQ了解一下?
by 梧桐灯 @ 2019-08-26 21:24:24
@脱发自动机 哦对我zz了,其实我一直想说的是倍增MLE……
by ⚡小林孑⚡ @ 2019-08-26 21:30:11
@光随影走 qwq