---

一、题意理解

1. 基本模型

• 地图：$n \times n$ 的网格。
• 敌人出现：$l$ 个时间点，第 $i$ 个时间在 $(x_i,y_i)$ 出现敌人。
• 炮塔特性：
  1. 射程：曼哈顿距离 $\le r$。
  2. 冷却：攻击后需 $k$ 时间冷却，即如果第 $i$ 时间攻击，下一次能攻击的时间是 $i+k$。
  3. 关键规则：如果炮塔射程内没有敌人，则立刻充能完毕（冷却清零）。
• 问题：对每个 $(p,q)$ 位置放置炮塔，计算它能消灭的最多敌人数量。

注意：炮塔攻击策略是自适应的：如果当前时间有敌人在射程内，且不处于冷却中，则必定攻击；如果没有敌人，则冷却清零，下次有敌人可立即攻击。

---

二、问题转化

1. 曼哈顿距离转化为切比雪夫距离

对于炮塔在 $(p,q)$，敌人出现在 $(x,y)$，条件 $|p-x|+|q-y|\le r$ 可以坐标变换：

令

$$u = p+q, \quad v = p-q$$

那么

$$|p-x|+|q-y| = \max(|u-(x+y)|, |v-(x-y)|)$$

实际上曼哈顿距离 $|p-x|+|q-y| \le r$ 等价于：

$$|u-(x+y)| \le r \quad\text{且}\quad |v-(x-y)| \le r $$

（注意这里是“且”不是“或”，这是曼哈顿距离的特性：曼哈顿距离 $\le r$ 等价于两个斜坐标方向上都差 $\le r$）

所以炮塔 $(p,q)$ 能攻击到 $(x,y)$ 当且仅当：

$$\begin{cases} x+y \in [u-r, u+r] \\ x-y \in [v-r, v+r] \end{cases} $$

2. 时间序列上的覆盖问题

对于固定的炮塔位置 $(p,q)$，对应固定的 $(u,v)$。

敌人按时间出现，我们关心哪些时间炮塔会攻击。
规则：炮塔冷却 $k$ 时间，但如果射程内没敌人，冷却清零。

所以问题转化为：在时间轴上，敌人出现的时间点被分为若干组，每组是连续的“有敌人在射程内”的时间段。
在一个连续段内，炮塔会每隔 $k$ 时间攻击一次（如果能攻击则攻击），但如果两个连续段之间有空隙（无敌人时间），则冷却清零，下一段从第一个时间就可以攻击。

---

三、高效计算所有位置

我们需要对每个 $(p,q)$ 计算，但 $n \le 2000$，直接枚举 $O(n^2 l)$ 不行。

观察到坐标变换后，$(u,v)$ 空间大小为 $(2n-1) \times (2n-1)$。

对于每个敌人出现的时间 $i$，位置 $(x_i,y_i)$ 对应：

$$U_i = x_i + y_i, \quad V_i = x_i - y_i + n \quad(\text{平移使下标从1开始}) $$

炮塔 $(p,q)$ 对应的 $(u,v)$ 要满足：

$$u \in [U_i-r, U_i+r], \quad v \in [V_i-r, V_i+r]$$

才能在第 $i$ 时间攻击到该敌人。

关键思路：在 $(u,v)$ 空间中，每个敌人出现时，对应一个矩形区域 $R_i$（曼哈顿距离 $\le r$ 的区域）。
对于炮塔位置 $(u,v)$，它能看到的时间序列就是那些矩形覆盖 $(u,v)$ 的时间点。

我们需要对每个 $(u,v)$ 计算：在这些覆盖它的时间点中，按照冷却规则最多能攻击多少次。

---

四、矩形覆盖的合并与差分

1. 冷却规则的重新表述

对于固定 $(u,v)$，设 $S$ 是覆盖它的时间点集合（已排序）。
将 $S$ 按连续性分段：如果 $t_j$ 和 $t_{j+1}$ 在 $S$ 中且 $t_{j+1} > t_j+1$，则它们属于不同段。

对于一段连续的时间 $[a,b]$，炮塔会在 $a, a+k, a+2k, \dots$ 攻击，直到超过 $b$。
设这段长度为 $L$，则攻击次数为 $\lfloor (L-1)/k \rfloor + 1$。

但如果段与段之间有空隙，冷却清零，下一段从第一个时间就可以攻击。

因此，总攻击次数 = 每段的攻击次数之和。

---

2. 时间分段的动态维护

我们从早到晚处理时间 $i=1$ 到 $l$，维护当前 $(u,v)$ 空间中被“当前连续段”覆盖的区域。

定义当前连续段：从某个起始时间 $t_0$ 到现在时间 $i$，矩形 $R_{t_0}, R_{t_0+1}, \dots, R_i$ 的交集非空，且中间没有中断（即每个时间矩形都与此交集有重叠）。

在 $(u,v)$ 空间上，这个“当前连续段”对应的区域是这些矩形的交集。
当我们处理时间 $i$ 时，如果 $R_i$ 与当前区域的交集非空，则当前段继续；否则当前段结束，开始新段。

新段开始时，区域就是 $R_i$ 本身；继续时，区域取交集。

---

3. 代码中的实现

3.1 矩形结构

struct rect {
    int x1, x2, y1, y2; // 在(u,v)空间的矩形边界
    int k; // 该连续段的起始时间
};
vector<rect> g; // 当前的所有连续段区域

3.2 处理每个时间点

对于时间 $i$：

1. 计算当前敌人的矩形 $R_i$：$[x1,x2] \times [y1,y2]$。
2. 更新所有 g 中的矩形：与 $R_i$ 取交集（即 v.x1 = max(v.x1, x1) 等）。
3. 删除无效矩形（交集为空）。
4. 如果 $g$ 为空，说明当前没有连续段覆盖 $(u,v)$，那么创建新段，区域为 $R_i$。
5. 如果 $g$ 非空，但 $R_i$ 可能比当前合并区域更大，那么将多出的部分作为新段加入：
   • 左、右、上、下超出当前合并区域的部分分别作为新矩形加入 g。

这样 g 中每个矩形对应一个连续段，其起始时间是 k，当前时间 $i$ 还在这个段中。

3.3 攻击计数

对于每个连续段矩形 $v$，如果 $(i - v.k) \% k == 0$，说明在这个段的这个时间点炮塔会攻击（因为从起始时间 $v.k$ 开始每隔 $k$ 时间攻击一次）。
那么对于这个矩形区域 $[v.x1,v.x2] \times [v.y1,v.y2]$，所有 $(u,v)$ 在这个区域的炮塔会在时间 $i$ 攻击。

因此，我们在这个矩形区域上 +1（差分数组 s 上做矩形加）。

---

4. 差分数组与最后输出

int s[4010][4010]; // (u,v)空间的差分数组
void add(int x1, int y1, int x2, int y2) {
    s[x1][y1]++;
    s[x1][y2+1]--;
    s[x2+1][y1]--;
    s[x2+1][y2+1]++;
}

最后做二维前缀和，得到每个 $(u,v)$ 的总攻击次数。

再通过坐标变换：

int gao1(int x, int y) { return x + y - 1; }
int gao2(int x, int y) { return x - y + n; }

将 $(u,v)$ 转回 $(p,q)$ 输出。

---

五、算法总结

1. 坐标变换：将曼哈顿距离 $\le r$ 转化为矩形区域。
2. 时间分段维护：动态维护 $(u,v)$ 空间上当前连续段覆盖的区域集合。
3. 矩形差分：对于每个连续段，在满足攻击条件的时间，对其区域全体 +1。
4. 前缀和：得到每个 $(u,v)$ 的总攻击次数，即炮塔最多消灭敌人数。

---

六、复杂度分析

• 每个时间点 $i$，g 中矩形数量很少（因为不断取交集，且新加部分有限），均摊 $O(1)$ 个。
• 每次对矩形做差分是 $O(1)$。
• 总时间 $O(l + n^2)$，空间 $O(n^2)$。

---

七、样例验证

样例：

n=2, l=2, r=1, k=1
(1,1) (2,2)

• 时间1：敌人 (1,1)，$U=2,V=1$（平移后）。矩形区域：$[1,3] \times [0,2]$（简化）。 创建新段，区域为此矩形，$i-k=0$ 整除 $k=1$，攻击，区域 +1。
• 时间2：敌人 (2,2)，$U=4,V=2$，矩形与当前段交集为空，结束旧段，创建新段。 攻击，新区域 +1。

最终 $(u,v)$ 空间：

• (1,1) 只被时间1覆盖：1次攻击。
• (2,2) 被时间1和2覆盖：但不在同一段（k=1），各段攻击1次，共2次。 对应回 $(p,q)$ 输出：

1 2
2 1

---

这个解法通过坐标变换将几何条件简化，通过动态维护连续段区域处理冷却规则，最后用矩形差分高效计算所有位置答案，是一道综合性强的好题。