本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-04-16 11:53:20

居然没有扫描线题解。
扫描线远远快于二维前缀和，我的二维前缀和是 CF 上最劣解，而扫描线是最优解。

做法

可以二分答案。

设当前二分到的时间是 $t$。

考虑如何判定。

显然被火烧过区域由一个个矩形组成。

而我们的主要任务是求出没被矩形覆盖的区域能不能通过再添加一个边长为 $2t+1$ 的矩形解决，即找到没覆盖点的纵坐标最大值，纵坐标最小值，横坐标最大值，横坐标最小值。
hy 考虑通过扫描线解决。

把所有的矩形分成两个竖线，第一个竖线代表这个矩形出现，第二个竖线代表这个矩形消失。

坐标虽然很大，把纵坐标离散化一下就解决了。

然后把所有竖线按照升序排列，依次处理。

如果第一条竖线横坐标大于 $1$，那么没覆盖纵坐标最大值和最小值直接确定为 $n$ 和 $1$，没覆盖最大最小横坐标对应更新一下。

每处理一条竖线，就利用线段树修改这条竖线对应区间，用当前最高和最低没覆盖点进行更新，如果这条竖线存在点没覆盖，那么还可以更新横坐标。

如果最后一条竖线后面有空的，再处理一下就行了。

关于线段树细节，树上每个点存储对应区间最高和最低没覆盖的点，然后常规维护就行了。

注意离散化如果不把 $1$ 和 $n$ 也离散化，会 Wrong answer on test10。

Code

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = a; i >= b; i--)
const int maxn = 3005;
int n, m, k;
struct Node
{
    int x, y;
    \/\/ 横坐标，纵坐标
} node[maxn];
ll lsh[maxn * 2];
int lshtop;
struct Line
{\/\/ 存储竖线信息
    ll x, y1, y2, mark;
    \/\/ y1 是这条竖线的上端点，y2 是下端点
} line[maxn * 2];
int linetop;
ll sgtcnt[maxn << 3], L[maxn << 3], R[maxn << 3], maxup[maxn << 3], mindw[maxn << 3];
\/\/ maxup 是最高的没覆盖点，min 是最低的没覆盖，注意这个是离散化之后的值
\/\/ sgtcnt 是当前区间被完全覆盖的次数
void build(int pos, int l, int r)
{
    sgtcnt[pos] = 0;
    L[pos] = l;
    R[pos] = r;
    maxup[pos] = r;
    mindw[pos] = l;
    if (l == r)
    {
        return;
    }
    int mid = (l + r) >> 1;
    build(pos << 1, l, mid);
    build(pos << 1 | 1, mid + 1, r);
}
void pushup(int now)
{
    if (sgtcnt[now])
    {
        maxup[now] = -5e9;
        mindw[now] = 5e9;
    }
    else
    {
        if (L[now] != R[now])
        {
            maxup[now] = max(maxup[now << 1], maxup[now << 1 | 1]);
            mindw[now] = min(mindw[now << 1], mindw[now << 1 | 1]);
        }
        else
        {
            maxup[now] = mindw[now] = L[now];
        }
    }
}
void change(int now, int l, int r, int val)
{
    if (l <= L[now] && R[now] <= r)
    {
        sgtcnt[now] += val;
        pushup(now);
        return;
    }
    if (L[now] > r || R[now] < l)
        return;
    int mid = (L[now] + R[now]) >> 1;
    if (mid >= l)
        change(now << 1, l, r, val);
    if (mid < r)
        change(now << 1 | 1, l, r, val);
    pushup(now);
}
bool check(ll time)
{
    lshtop = 0, linetop = 0;
    FOR(i, 1, k)
    {
        lsh[++lshtop] = min(1ll * n, node[i].y + time);
        lsh[++lshtop] = max(1ll, node[i].y - time);
        lsh[++lshtop] = min(1ll * n, node[i].y + time + 1);
        lsh[++lshtop] = max(1ll, node[i].y - time - 1);
        lsh[++lshtop] = min(1ll * n, max(1ll,node[i].y + time - 1));
        lsh[++lshtop] = max(1ll, min(1ll*n,node[i].y - time + 1));
    }
    lsh[++lshtop] = 1;
    lsh[++lshtop] = n;
    sort(lsh + 1, lsh + lshtop + 1);
    lshtop = unique(lsh + 1, lsh + lshtop + 1) - lsh - 1;
    \/\/ 离散化
    FOR(i, 1, k)
    {
        int nwy1 = lower_bound(lsh + 1, lsh + lshtop + 1, min(1ll * n, node[i].y + time)) - lsh;
        int nwy2 = lower_bound(lsh + 1, lsh + lshtop + 1, max(1ll, node[i].y - time)) - lsh;
        \/\/ 计算离散化之后的 y

        line[++linetop] = {max(1ll, node[i].x - time), nwy1, nwy2, 1};
        line[++linetop] = {min(1ll * m, node[i].x + time) + 1, nwy1, nwy2, -1};
        \/\/ 竖线
        \/\/ 第二条线代表删除这个矩形
    }
    sort(line + 1, line + linetop + 1, [&](Line &a, Line &b)
         {  if(a.x!=b.x)
                return a.x < b.x; 
            else
                return a.mark>b.mark; });\/\/ 对竖线按横坐标升序排列。  
    build(1, 1, lshtop);\/\/ 建树
    ll maxupf = -5e9, mindwf = 5e9, maxrigf = -5e9, minleff = 5e9;
    if (line[1].x > 1)
    {\/\/ 前面有空的区域
        maxupf = n;
        mindwf = 1;
        minleff = 1;
        maxrigf = line[1].x - 1;
        \/\/       puts("Updated\n");
    }
    int cnt = 0;
    int posx=0;
    ll before_x = 0;
    FOR(i, 1, linetop)
    {\/\/ 运行扫描线
        if (line[i].x > m)
            break;
        change(1, line[i].y2, line[i].y1, line[i].mark);

        cnt++; \/\/ 计算到目前为止还有多少竖线没处理
        posx=line[i].x;
        if (line[i].x != line[i + 1].x)
        {
            cnt = 0;
            if (mindw[1] != 5e9)
            {
                maxupf = max(maxupf, lsh[maxup[1]]);
                mindwf = min(mindwf, lsh[mindw[1]]);
                maxrigf = max(maxrigf, line[i + 1].x - 1);
                minleff = min(minleff, before_x + 1);
            }
                before_x = line[i].x;
        }
    } 
    if (line[linetop].x < m)
    {\/\/ 后面有空的区域
        maxupf = n;
        mindwf = 1;
        maxrigf = m;
        minleff = min(minleff, line[linetop].x  + 1);
    }
    return ((maxupf - mindwf + 1 <= time * 2  + 1) && (maxrigf - minleff + 1 <= time * 2 +1));
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    FOR(i, 1, k)
    {
        scanf("%d%d", &node[i].x, &node[i].y);
        swap(node[i].x, node[i].y);
    }
    int l = 0, r = 1e9;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    printf("%d", l);
    return 0;
}