Codeforces 1262E Arson In Berland Forest（二维前缀和+二维差分+二分）

 题意是需要求最大的扩散时间，最后输出的是一开始的火源点，那么我们比较容易想到的是二分找最大值，但是我们在这满足这样的点的时候可以发现，在当前扩散时间k下,以这个点为中心的(2k+1)的正方形块内必须全部都是'X'才行，那么要访问这样的块内的'X'个数显然需要使用二维前缀和维护一下就可以O(1)求出个数，那么这部分问题我们解决，接下来就是二分的如何Check,那么既然我们之前找到了这样满足当期扩散时间的点后，我们只需要直接将这块矩形内部的点全部打标记，显然我们可以得知，如果当前扩散时间是满足要求的，那么所有的'X'最后都会被打上标记，那么我们可以利用这一性质，对满足这样的矩形进行二维差分，最后O(n*m)把标记推掉，在check一遍所有被打伤标记的点是不是等于等于一开始'X'的个数，若等于，那么我们可以将区间移至右边，否则移至左边。

最后记得不要用cin，cout，T的死去活来.....

 //      ——By DD_BOND

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int MAXN=1e6+;

 inline ll sqr(ll x){ return x*x; }

 char s[MAXN];

 int main(void)

 {

     int n,m;    scanf("%d%d",&n,&m);

     vector<vector<int> >ok (n+,vector<int>(m+));

     vector<vector<int> >sum(n+,vector<int>(m+));

     vector<vector<int> >tmp(n+,vector<int>(m+));

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

         scanf("%s",s+);

         for(int j=;j<=m;j++)    if(s[j]=='X')   sum[i][j]=;

     }

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             sum[i][j]+=sum[i-][j]+sum[i][j-]-sum[i-][j-];

     int l=,r=(min(n,m)-)/,res=;

     while(l<=r){

         int mid=(l+r)>>;

         for(int i=;i<=n;i++)

             for(int j=;j<=m;j++)

                 tmp[i][j]=;

         for(int i=mid+;i<=n-mid;i++)

             for(int j=mid+;j<=m-mid;j++)

                 if(sum[i+mid][j+mid]-sum[i-mid-][j+mid]-sum[i+mid][j-mid-]+sum[i-mid-][j-mid-]==sqr(*mid+)){

                     tmp[i-mid][j-mid]+=;

                     tmp[i-mid][j+mid+]+=-;

                     tmp[i+mid+][j-mid]+=-;

                     tmp[i+mid+][j+mid+]+=;

                 }

         int f=;

         for(int i=;i<=n;i++)

             for(int j=;j<=m;j++)

                 if(tmp[i][j]+=tmp[i-][j]+tmp[i][j-]-tmp[i-][j-])

                     f++;

         if(f==sum[n][m])   l=mid+,res=mid;

         else    r=mid-;

     }

     printf("%d\n",res);

     for(int i=res+;i<=n-res;i++)

         for(int j=res+;j<=m-res;j++)

             if(sum[i+res][j+res]-sum[i-res-][j+res]-sum[i+res][j-res-]+sum[i-res-][j-res-]==sqr(*res+))

                 ok[i][j]=;

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

         for(int j=;j<=m;j++)   putchar((ok[i][j]?'X':'.'));

         puts("");

     }

     return ;

 }