题解：

问题分析

本题要求计算一个$N \times M$网格中，所有标记为$Q$的格子数量。标记规则为：有僵尸的格子标记为$0$，然后依次标记相邻格子为$1, 2, 3, ...$，直到所有格子都被标记。

关键观察：

1. 标记值其实就是该格子到最近僵尸的切比雪夫距离：distance = max(|x1-x2|, |y1-y2|)
2. 网格巨大($N,M \leq 10^9$)，无法直接模拟
3. 僵尸数量$K \leq 2000$，相对较少

算法思路

由于$K \leq 2000$，我们可以基于僵尸点进行计算。核心思想：

1. 对于每个查询$Q$，计算所有距离小于$Q$的格子数
2. 距离为$Q$的格子数 = 距离$< Q+1$的格子数 - 距离$< Q$的格子数
3. 计算距离$< d$的格子数可以转化为计算所有僵尸扩展$d-1$步后覆盖的格子数并集

具体实现使用平面扫描线算法：

C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_K 2010
#define INF 1000000000

typedef long long ll;

typedef struct {
    int x, y;
} Point;

typedef struct {
    int x, y1, y2;
    int type; // 1: 进入, -1: 离开
} Event;

Point zombies[MAX_K];
Event events[MAX_K * 2];
int temp_y[MAX_K * 2];

// 比较函数：按x坐标排序
int cmp_points(const void *a, const void *b) {
    Point *p1 = (Point *)a;
    Point *p2 = (Point *)b;
    return (p1->x != p2->x) ? (p1->x - p2->x) : (p1->y - p2->y);
}

// 事件比较函数
int cmp_events(const void *a, const void *b) {
    Event *e1 = (Event *)a;
    Event *e2 = (Event *)b;
    return (e1->x != e2->x) ? (e1->x - e2->x) : (e2->type - e1->type);
}

// 计算距离<d的格子数量
ll count_cells_less_than_d(int N, int M, int K, int d) {
    if (d <= 0) return 0;
    if (d > N + M) d = N + M; // 最大可能距离
    
    int event_cnt = 0;
    int y_cnt = 0;
    
    // 对于每个僵尸，创建矩形
    for (int i = 0; i < K; i++) {
        int x = zombies[i].x;
        int y = zombies[i].y;
        
        // 矩形边界：僵尸点扩展d-1步
        int left = x - (d - 1);
        int right = x + (d - 1);
        int top = y - (d - 1);
        int bottom = y + (d - 1);
        
        // 裁剪到网格范围内
        if (left > M || right < 1 || top > N || bottom < 1) continue;
        if (left < 1) left = 1;
        if (right > M) right = M;
        if (top < 1) top = 1;
        if (bottom > N) bottom = N;
        
        // 创建事件
        events[event_cnt++] = (Event){left, top, bottom, 1};
        events[event_cnt++] = (Event){right + 1, top, bottom, -1};
        
        temp_y[y_cnt++] = top;
        temp_y[y_cnt++] = bottom;
    }
    
    if (event_cnt == 0) return 0;
    
    // 对事件按x排序
    qsort(events, event_cnt, sizeof(Event), cmp_events);
    
    // 对y坐标去重排序
    qsort(temp_y, y_cnt, sizeof(int), 
          (int (*)(const void *, const void *))cmp_int);
    int unique_y_cnt = 0;
    for (int i = 0; i < y_cnt; i++) {
        if (i == 0 || temp_y[i] != temp_y[i-1]) {
            temp_y[unique_y_cnt++] = temp_y[i];
        }
    }
    
    // 创建线段树(简化版：差分数组)
    ll *cover = (ll *)calloc(unique_y_cnt * 2, sizeof(ll));
    ll *len = (ll *)calloc(unique_y_cnt * 2, sizeof(ll));
    
    ll total_area = 0;
    int last_x = events[0].x;
    
    for (int i = 0; i < event_cnt; i++) {
        int x = events[i].x;
        
        // 计算当前x之前的面积
        if (x > last_x) {
            ll segment_len = 0;
            for (int j = 0; j < unique_y_cnt - 1; j++) {
                if (cover[j] > 0) {
                    segment_len += temp_y[j+1] - temp_y[j] + 1;
                }
            }
            total_area += segment_len * (x - last_x);
        }
        
        // 更新覆盖
        int y1 = events[i].y1;
        int y2 = events[i].y2;
        int type = events[i].type;
        
        // 查找y1, y2在temp_y中的位置
        int idx1 = -1, idx2 = -1;
        for (int j = 0; j < unique_y_cnt; j++) {
            if (temp_y[j] == y1) idx1 = j;
            if (temp_y[j] == y2) idx2 = j;
        }
        
        if (idx1 != -1 && idx2 != -1) {
            // 更新区间[idx1, idx2]的覆盖
            for (int j = idx1; j < idx2; j++) {
                cover[j] += type;
            }
        }
        
        last_x = x;
    }
    
    free(cover);
    free(len);
    
    return total_area;
}

// 计算距离恰好等于Q的格子数量
ll count_cells_exactly_Q(int N, int M, int K, int Q) {
    if (Q < 0) return 0;
    
    // 距离恰好为0的格子就是僵尸所在的格子
    if (Q == 0) return K;
    
    // 距离恰好为Q的格子数 = 距离<Q+1的格子数 - 距离<Q的格子数
    ll less_than_Q_plus_1 = count_cells_less_than_d(N, M, K, Q + 1);
    ll less_than_Q = count_cells_less_than_d(N, M, K, Q);
    
    return less_than_Q_plus_1 - less_than_Q;
}

int main() {
    int N, M, K, Q;
    scanf("%d %d", &N, &M);
    scanf("%d", &K);
    
    for (int i = 0; i < K; i++) {
        scanf("%d %d", &zombies[i].x, &zombies[i].y);
    }
    
    scanf("%d", &Q);
    
    // 注意：题目输入的行列可能和我们的坐标系相反
    // 这里假设输入是(行, 列)，我们转换成(x, y)坐标
    
    ll result = count_cells_exactly_Q(N, M, K, Q);
    printf("%lld\n", result);
    
    return 0;
}

算法详细解释

1. 切比雪夫距离计算

每个格子的标记值 = 到最近僵尸的切比雪夫距离：

distance = max(|x1 - x2|, |y1 - y2|)

这意味着距离为$d$的格子形成了一个以僵尸为中心的正方形环。

2. 平面扫描线算法

要计算所有距离$< d$的格子数，我们需要计算所有僵尸扩展$d-1$步后覆盖的格子数并集。

对于每个僵尸$(x, y)$，扩展$d-1$步后覆盖的矩形为：

• 左边界：max(1, x - (d-1))
• 右边界：min(M, x + (d-1))
• 上边界：max(1, y - (d-1))
• 下边界：min(N, y + (d-1))

我们需要计算这些矩形的并集面积。

3. 事件处理

将每个矩形的左右边界作为事件：

• 左边界：(left, y1, y2, 1) 表示进入
• 右边界：(right+1, y1, y2, -1) 表示离开

按x坐标排序事件，从左到右扫描，维护当前x处y方向的覆盖情况。

4. 面积计算

对于每个x区间[last_x, current_x)：

• 计算当前y方向被覆盖的总长度
• 面积 = 覆盖长度 × (current_x - last_x)
• 累加到总面积

5. 最终答案

距离恰好为$Q$的格子数 = 距离$< Q+1$的格子数 - 距离$< Q$的格子数

优化版本（更高效）

上面的实现为了清晰展示了算法思路，但对于大量矩形可能需要优化。以下是更高效的版本：

// 更高效的矩形面积并计算
ll compute_union_area(int N, int M, int K, int d) {
    if (d <= 0) return 0;
    
    // 压缩y坐标
    ll *y_coords = (ll *)malloc((K * 2 + 5) * sizeof(ll));
    int y_count = 0;
    
    // 收集所有矩形的y坐标
    for (int i = 0; i < K; i++) {
        int y = zombies[i].y;
        int top = y - (d - 1);
        int bottom = y + (d - 1);
        
        if (top < 1) top = 1;
        if (bottom > N) bottom = N;
        
        y_coords[y_count++] = top;
        y_coords[y_count++] = bottom + 1; // 使用[top, bottom+1)区间
    }
    
    // 排序去重
    qsort(y_coords, y_count, sizeof(ll), 
          (int (*)(const void *, const void *))cmp_ll);
    
    int unique_y = 0;
    for (int i = 0; i < y_count; i++) {
        if (i == 0 || y_coords[i] != y_coords[i-1]) {
            y_coords[unique_y++] = y_coords[i];
        }
    }
    
    // 差分数组
    int *diff = (int *)calloc(unique_y, sizeof(int));
    
    // 处理事件
    Event *events = (Event *)malloc((K * 2 + 5) * sizeof(Event));
    int event_count = 0;
    
    for (int i = 0; i < K; i++) {
        int x = zombies[i].x;
        int y = zombies[i].y;
        
        int left = x - (d - 1);
        int right = x + (d - 1);
        int top = y - (d - 1);
        int bottom = y + (d - 1);
        
        if (left > M || right < 1 || top > N || bottom < 1) continue;
        if (left < 1) left = 1;
        if (right > M) right = M;
        if (top < 1) top = 1;
        if (bottom > N) bottom = N;
        
        // 查找y区间
        int idx1 = lower_bound(y_coords, unique_y, top);
        int idx2 = lower_bound(y_coords, unique_y, bottom + 1);
        
        events[event_count++] = (Event){left, idx1, idx2, 1};
        events[event_count++] = (Event){right + 1, idx1, idx2, -1};
    }
    
    qsort(events, event_count, sizeof(Event), cmp_events);
    
    ll total_area = 0;
    int last_x = 0;
    
    for (int i = 0; i < event_count; i++) {
        int x = events[i].x;
        
        // 计算上一个x到当前x的面积
        if (x > last_x) {
            ll covered_length = 0;
            int current_cover = 0;
            
            for (int j = 0; j < unique_y - 1; j++) {
                current_cover += diff[j];
                if (current_cover > 0) {
                    covered_length += y_coords[j+1] - y_coords[j];
                }
            }
            
            total_area += covered_length * (x - last_x);
        }
        
        // 更新覆盖
        int idx1 = events[i].y1;
        int idx2 = events[i].y2;
        int type = events[i].type;
        
        for (int j = idx1; j < idx2; j++) {
            diff[j] += type;
        }
        
        last_x = x;
    }
    
    free(y_coords);
    free(diff);
    free(events);
    
    return total_area;
}

复杂度分析

• 时间：$O(K^2 \log K)$，其中$K \leq 2000$
• 空间：$O(K)$

注意事项

1. 注意网格边界处理
2. 小心整数溢出，使用long long
3. 对于$Q=0$的特殊情况直接返回$K$
4. 当$Q$很大时，所有格子可能都被覆盖，需要特别处理

这个算法能够处理$10^9 \times 10^9$的巨大网格，因为只依赖僵尸数量$K$，不依赖网格大小。