题解：P2716 和谐的雪花

· · 题解

提供一种二分加二维线段树的算法。

题目大意

给定 n，m，k 和一个 n \times m 的矩阵。定义一个正方形的优美值为其最大值和最小值的差，要最小化优美值大于 k 正方形边长。

思路

在我们增加正方形边长时，会发现矩阵最大的这种正方形的优美值单调递增。于是二分答案，枚举起点，然后用二维线段树统计该种的最大优美值。

代码

#include<bits/stdc++.h>
#define int long long 
#define Maxn 501
using namespace std;
int a[Maxn][Maxn];
int maxn[Maxn*4][Maxn*4];
int minv[Maxn*4][Maxn*4];
int Max,Min;
int m,n;
//线段树模板
void pushup1(int x1,int x2) {
    maxn[x1][x2]=max(maxn[x1<<1][x2],maxn[x1<<1|1][x2]);
    minv[x1][x2]=min(minv[x1<<1][x2],minv[x1<<1|1][x2]);
}
void pushup2(int x1,int x2) {
    maxn[x1][x2]=max(maxn[x1][x2<<1],maxn[x1][x2<<1|1]);
    minv[x1][x2]=min(minv[x1][x2<<1],minv[x1][x2<<1|1]);
}
void build2(int x1,int x2,int l,int r,int flag)
{
    if(l == r) {
        if(flag != -1)
        maxn[x1][x2]=minv[x1][x2]=a[flag][l];
        else pushup1(x1,x2);
        return;
    }
    int mid=l+r>>1;
    build2(x1,x2<<1,l,mid,flag);
    build2(x1,x2<<1|1,mid+1,r,flag);
    pushup2(x1,x2);
}

void build1(int x1,int l,int r)
{
    if(l == r) {
        build2(x1,1,1,m,l);
        return;
    }
    int mid=l+r>>1;
    build1(x1<<1,l,mid);
    build1(x1<<1|1,mid+1,r);
    build2(x1,1,1,m,-1);
}
void query2(int x1,int x2,int l,int r,int y1,int y2)
{
    if(l>=y1&&r<=y2) {
        Max=max(Max,maxn[x1][x2]);
        Min=min(Min,minv[x1][x2]);
        return;
    }
    int mid=l+r>>1;
    if(y1<=mid)query2(x1,x2<<1,l,mid,y1,y2);
    if(y2>mid)query2(x1,x2<<1|1,mid+1,r,y1,y2);
}
void query1(int u1,int l,int r,int x1,int x2,int y1,int y2)
{
    if(l>=x1&&r<=x2) {
        query2(u1,1,1,m,y1,y2);
        return;
    }
    int mid=l+r>>1;
    if(x1<=mid)query1(u1<<1,l,mid,x1,x2,y1,y2);
    if(x2>mid)query1(u1<<1|1,mid+1,r,x1,x2,y1,y2);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    build1(1,1,n);
    //二分答案
    int l=1,r=min(n,m),ans=-1,mid;
    while(l<=r)
    {
        mid=l+r>>1;
        int res=-1;
        for(int i=1;i<=n-mid+1;i++)
            for(int j=1;j<=m-mid+1;j++)
                Max=-INT_MAX,Min=INT_MAX,
                query1(1,1,n,i,i+mid-1,j,j+mid-1),
                res=max(res,Max-Min);
        //枚举正方形，求最大优美值
        if(k<=res)ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}