蒟蒻求助,为什么有三个点MLE了????

P1886 滑动窗口 /【模板】单调队列

[已注销]!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


上一页 |