BZOJ2702 : 金融风暴

求出离每个点最近的关键点，然后用二维ST表回答正方形最大值。

将关键点分为上下两部分，以上为例：

从上到下依次考虑每一行，记录每一列往上最近的关键点的距离，那么最优决策具有单调性，可以分治求解。

时间复杂度$O(n^2\log n+t)$。

#include<cstdio>

#include<cmath>

const int N=1005,inf=N*N+N*N,BUF=27000000;

int n,m,i,j,k,x,y,z,f[N],g[N],Log[N],d[10][N][N];bool is[N][N],flag;

char Buf[BUF],*buf=Buf;

inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}

void solve(int l,int r,int dl,int dr){

  int m=(l+r)>>1,&ret=g[m],dm;

  for(int i=dl;i<=dr;i++)if(~f[i]){

    int t=(m-i)*(m-i)+f[i]*f[i];

    if(t<ret)ret=t,dm=i;

  }

  if(l<m)solve(l,m-1,dl,dm);

  if(r>m)solve(m+1,r,dm,dr);

}

inline int max(int a,int b){return a>b?a:b;}

inline int ask(int x,int y,int k){

  int o=Log[k];

  return max(max(d[o][x][y],d[o][x+k-(1<<o)][y]),max(d[o][x][y+k-(1<<o)],d[o][x+k-(1<<o)][y+k-(1<<o)]));

}

int main(){

  fread(Buf,1,BUF,stdin);read(n),read(m),read(k);

  for(i=2;i<=n||i<=m;i++)Log[i]=Log[i>>1]+1;

  while(k--)read(x),read(y),is[x][y]=1;

  for(i=0;i<=m;i++)f[i]=-1;

  for(i=0;i<=n;i++){

    for(j=0;j<=m;j++){

      if(is[i][j])f[j]=0,flag=1;else if(~f[j])f[j]++;

      g[j]=inf;

    }

    if(flag)solve(0,m,0,m);

    for(j=0;j<=m;j++)d[0][i][j]=g[j];

  }

  for(flag=i=0;i<=m;i++)f[i]=-1;

  for(i=n;~i;i--){

    for(j=0;j<=m;j++){

      if(is[i][j])f[j]=0,flag=1;else if(~f[j])f[j]++;

      g[j]=inf;

    }

    if(flag)solve(0,m,0,m);

    for(j=0;j<=m;j++)if(d[0][i][j]>g[j])d[0][i][j]=g[j];

  }

  for(k=1;k<10;k++)for(i=0;i+(1<<k)-1<=n;i++)for(j=0;j+(1<<k)-1<=m;j++)d[k][i][j]=max(max(d[k-1][i][j],d[k-1][i+(1<<(k-1))][j]),max(d[k-1][i][j+(1<<(k-1))],d[k-1][i+(1<<(k-1))][j+(1<<(k-1))]));

  read(k);

  while(k--){

    read(x),read(y),read(z);

    if(x<z||x+z>n||y<z||y+z>m){puts("-1");continue;}

    printf("%.3f\n",std::sqrt(ask(x-z,y-z,z<<1|1)));

  }

  return 0;

}