分块90求救!

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

高能一号 @ 2017-07-21 14:09:16

RT,怎么调都要T一个点

#include<stdio.h>
#include<cmath>
#define N 1000005
#define M 40001
#define oo 2147483647
#define For(i,j,k) for(int i=j;i<=k;++i)
using namespace std;
int read(){
    int l=1,x=0; char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') ch=getchar(),l=-1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*l;
}
int a[N],bel[N],blockmax[M],blockmin[M],bl[M],br[M],maxn[N];
int main(){
    int n=read(),m=read(),ma,mi,l,r,sqn,sum;
    sqn=pow(n,2.0/8.3); sum=n/sqn; if (sum%sqn) sum++; //printf("%d ",sqn);
    For(i,1,n) a[i]=read();
    For(i,1,sum-1){
        bl[i]=(i-1)*sqn+1; br[i]=i*sqn;
        ma=-oo; mi=oo;
        For(j,bl[i],br[i]) {
            bel[j]=i;
            if (a[j]>=ma) ma=a[j];
            if (a[j]<=mi) mi=a[j];
        }
        blockmax[i]=ma; blockmin[i]=mi;
    }
    bl[sum]=br[sum-1]+1; br[sum]=n;
    ma=-oo; mi=oo;
    For(j,bl[sum],br[sum]){
        bel[j]=sum;
        if (a[j]>=ma) ma=a[j];
        if (a[j]<=mi) mi=a[j];
    }
    blockmax[sum]=ma; blockmin[sum]=mi;
    For(i,1,n-m+1){
        l=i; r=i+m-1;
        ma=-oo; mi=oo;
        if (bel[l]==bel[r]) 
            For(j,l,r){
                if (a[j]>=ma) ma=a[j];
                if (a[j]<=mi) mi=a[j];
            }
        else{
            For(j,l,br[bel[l]]){
                if (a[j]>=ma) ma=a[j];
                if (a[j]<=mi) mi=a[j];
            }
            For(j,bel[l]+1,bel[r]-1){
                if (ma<=blockmax[j]) ma=blockmax[j];
                if (mi>=blockmin[j]) mi=blockmin[j];
             }
             For(j,bl[bel[r]],r){
                 if (a[j]>=ma) ma=a[j];
                if (a[j]<=mi) mi=a[j];
             }
        }
        printf("%d ",mi); maxn[i]=ma;
    }
    printf("\n");
    For(i,1,n-m+1) printf("%d ",maxn[i]);
    return 0;
}
@远航之曲

by 1124828077ccj @ 2017-07-21 17:51:52

@高能一号 这题正解是单调队列。。。分块你算算时间复杂度。。。


by 高能一号 @ 2017-07-22 14:47:24

@2016陈常杰 可是我只T了一个啊


by 1124828077ccj @ 2017-07-22 20:32:29

@高能一号 这题数据真的很弱,我当时爆搜加了个优化就过了。。。


|