233的网格图 - 题解
标签与难度
标签: CDQ分治, 二维数点, 离线算法, 树状数组, 坐标转换, 曼哈顿距离, 切比雪夫距离 难度: 2500
题目大意喵~
你好呀，指挥官！这道题是关于一个网格图上的点点们的说~
我们一开始有 个点，每个点都有一个坐标 。两点 和 之间的距离被定义为曼哈顿距离，也就是 。
接下来，我们需要处理 次操作，操作有三种类型，喵：
- 查询
1: 计算一下，当前有多少对点 (这里我们默认 )，它们之间的曼哈顿距离小于或等于一个给定的值 呢？ - 修改
2 u: 将距离参数 更新为 。 - 修改
3 u x y: 将第 个点的坐标修改为 。
我们需要对每次查询操作，都给出正确的答案，呐。
解题思路分析
这道题看起来有点复杂呢，又是动态修改点，又是修改距离参数 的。不过别担心，跟着我的思路一步步来，就能把它变成一只温顺的小猫咪~ 喵~
Step 1: 距离的奇妙变身！
首先，我们来处理这个有点棘手的曼哈顿距离。直接处理 这个带有绝对值和加法的式子，会非常麻烦。
这里有一个超级经典的技巧，叫做坐标系旋转45度！我们把每个点 映射到一个新的坐标系下，变成 。
让我们看看在这个新坐标系下，距离会变成什么样吧！ 原坐标系两点 和 。 新坐标系两点 和 。
一个神奇的数学恒等式是：。 令 ，，我们就能得到：
也就是说，原来坐标系下的曼哈顿距离，等于新坐标系下的切比雪夫距离！
那么，原来的距离条件 就等价于： 这又可以拆成两个独立的条件：
哇！问题转化成：对于每个点 ，我们需要统计有多少个点 落在以 为中心、边长为 的正方形区域内。这是一个二维数点问题，比原来好处理多啦！
Step 2: 应对动态变化——离线处理与分批
题目中的操作是动态的，特别是修改 的操作，它会影响所有点对的距离判断，非常麻烦。
注意到当 发生变化时，之前的计算几乎都作废了。这启发我们，可以把操作根据 的变化分成几个批次。在一个批次内， 的值是固定的。我们只需要处理这个批次内的点坐标修改和查询操作。
对于一个批次内的操作，我们可以在最后统一计算。这种把操作攒起来一起处理的方法，就叫离线算法。
Step 3: 终极武器——CDQ分治
在一个固定的 的批次内，我们有一系列点的修改和查询。一个点的修改可以看作是“删除一个旧点”和“增加一个新点”。 一次查询，是问当前所有点中，满足距离条件的点对总数。
如果我们从头开始模拟，每次查询都重新计算一遍，太慢了。如果我们跟踪总数的变化，每次点修改后，计算这个修改对总数的影响，就需要一个支持动态增删和查询的数据结构，也很复杂。
让我们换个思路。我们要求的是 。直接计算这个带有 限制的式子，是一个三维偏序问题（维度分别是 , , ）。
不过，参考代码给了一种更巧妙的计算方式。我们先计算一个更容易的值：。 这个 计算了所有点对 （包括 和 ）的贡献。
- 当 时，距离为0，肯定满足条件，这部分贡献了 。
- 当 时，点对 和 被计算了两次。 所以，我们要求的答案就是 。
可以表示为 。邻居数就是满足距离条件的其它点的数量。 所以，问题变成了，对于每个点 ，计算在它周围的 -邻域正方形内有多少个点。
我们将一个批次内的所有操作（初始点、点增加、点删除）都看作事件。
- 一个初始点，是在时刻0增加一个点。
- 一次修改，是在某个时刻删除一个点，同时增加一个新点。
- 一次查询，是询问某个时刻的 值。
我们可以用 ans[t] 记录在第 t 次查询时的 值。 的值可以通过前一时刻的 值加上变化量得到。变化量来自于点的增删。
- 增加一个点 ： 增加
(P的邻居数 + 1)。 - 删除一个点 ： 减少
(P的邻居数 + 1)。
所以，核心问题就变成了：对于每个增删的点 ，计算它有多少个邻居。这又回到了我们的二维数点问题：查询一个正方形区域内的点数。
这个问题可以用CDQ分治来高效地解决！ 我们将一个批次内的所有事件（点本身作为“数据点”，以及由点增删产生的“查询矩形”）混合在一起，用CDQ分治来处理。
CDQ分治流程, 喵~:
- 事件化：
- 每个点 既是一个数据点，也产生一个查询。
- 查询“的邻居数”等价于查询矩形
[x'_i-k, x'_i+k] x [y'_i-k, y'_i+k]。 - 使用二维前缀和/差分思想，将一个矩形查询拆成4个角的顶点查询。例如，查询矩形
[x1, x2] x [y1, y2]的点数 =count(x2, y2) - count(x1-1, y2) - count(x2, y1-1) + count(x1-1, y1-1)。 - 于是，所有操作都变成了两种基本事件：
(x', y', type, weight):type=DATA表示这是一个数据点。(x', y', type, weight, time_id):type=QUERY表示这是一个查询点，time_id对应第几次查询。
- 分治：
solve_cdq(l, r)处理事件序列[l, r]。- 递归处理左半部分
solve_cdq(l, mid)和右半部分solve_cdq(mid+1, r)。 - 计算跨区间的贡献：计算左半部分
[l, mid]的数据点对右半部分[mid+1, r]的查询的贡献。 - 为此，我们将
[l, mid]和[mid+1, r]按 坐标排序。 - 使用扫描线：从左到右扫描 坐标。同时维护一个以 坐标为下标的树状数组(BIT)。
- 当扫描到一个来自左半部分的数据点时，将其 坐标加入树状数组。
- 当扫描到一个来自右半部分的查询点时，在树状数组中查询，计算贡献，并累加到对应的
ans[time_id]上。 - 分治结束后，
ans数组里就存储了每个查询时刻 值的变化量。
- 统计答案：
- 对
ans数组求前缀和，就能得到每个查询时刻 的绝对值。 - 对于第
t次查询，最终答案就是(ans[t] - N) / 2。
- 对
这样，通过坐标转换、离线处理和CDQ分治，我们就能高效地解决这个问题啦！是不是很厉害，喵！
代码实现
这是我根据上面的思路，精心重构的代码哦~ 变量名和注释都写得很清楚，希望能帮到你，喵~
cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 100005;
// 定义点的结构体（原始坐标）
struct Point {
long long x, y;
};
// 定义事件的结构体
enum EventType {
DATA_POINT, // 数据点
QUERY_CORNER // 查询矩形的角点
};
struct Event {
long long x, y; // 变换后的坐标
EventType type;
int weight; // 权重 (+1 或 -1)
int time_id; // 属于第几次查询
// 为了排序
bool operator<(const Event& other) const {
if (x != other.x) {
return x < other.x;
}
// 数据点优先处理，确保在同一x坐标时，点先于查询被处理
return type < other.type;
}
};
int n;
long long k;
int q;
Point points[MAXN];
vector<Event> events;
vector<long long> discrete_y; // 用于y坐标离散化
long long query_results[MAXN];
long long bit[MAXN * 10]; // 树状数组
void update_bit(int idx, int delta) {
for (; idx < discrete_y.size(); idx += idx & -idx) {
bit[idx] += delta;
}
}
long long query_bit(int idx) {
long long sum = 0;
for (; idx > 0; idx -= idx & -idx) {
sum += bit[idx];
}
return sum;
}
// 获取y坐标离散化后的索引
int get_y_idx(long long y_val) {
return lower_bound(discrete_y.begin(), discrete_y.end(), y_val) - discrete_y.begin() + 1;
}
// 将一个点的贡献（作为数据点和查询矩形）加入事件列表
void add_point_events(int p_idx, int time, int weight) {
long long cur_x = points[p_idx].x;
long long cur_y = points[p_idx].y;
// 坐标变换
long long tx = cur_x + cur_y;
long long ty = cur_y - cur_x;
// 1. 作为数据点
events.push_back({tx, ty, DATA_POINT, weight, time});
// 2. 作为查询矩形，拆成4个角点
long long x1 = tx - k, x2 = tx + k;
long long y1 = ty - k, y2 = ty + k;
events.push_back({x2, y2, QUERY_CORNER, weight, time});
events.push_back({x1 - 1, y2, QUERY_CORNER, -weight, time});
events.push_back({x2, y1 - 1, QUERY_CORNER, -weight, time});
events.push_back({x1 - 1, y1 - 1, QUERY_CORNER, weight, time});
}
void solve_cdq(int l, int r) {
if (l >= r) {
return;
}
int mid = l + (r - l) / 2;
solve_cdq(l, mid);
solve_cdq(mid + 1, r);
vector<Event> left_events, right_events;
for (int i = l; i <= mid; ++i) {
if (events[i].type == DATA_POINT) {
left_events.push_back(events[i]);
}
}
for (int i = mid + 1; i <= r; ++i) {
if (events[i].type == QUERY_CORNER) {
right_events.push_back(events[i]);
}
}
// 按x坐标排序，进行扫描线
sort(left_events.begin(), left_events.end());
sort(right_events.begin(), right_events.end());
int p_left = 0;
for (const auto& q_event : right_events) {
while (p_left < left_events.size() && left_events[p_left].x <= q_event.x) {
update_bit(get_y_idx(left_events[p_left].y), left_events[p_left].weight);
p_left++;
}
query_results[q_event.time_id] += (long long)q_event.weight * query_bit(get_y_idx(q_event.y));
}
// 清理树状数组
for (int i = 0; i < p_left; ++i) {
update_bit(get_y_idx(left_events[i].y), -left_events[i].weight);
}
// inplace_merge保持按x排序，为上层递归做准备
inplace_merge(events.begin() + l, events.begin() + mid + 1, events.begin() + r + 1);
}
// 处理一个批次的操作
void process_batch() {
if (events.empty()) return;
// 收集所有y坐标用于离散化
discrete_y.clear();
for (const auto& ev : events) {
discrete_y.push_back(ev.y);
if (ev.type == QUERY_CORNER) {
// 查询矩形的y坐标也需要加入
// tx, ty 是变换后的点坐标
// y1 = ty-k, y2 = ty+k
// y1-1 和 y2
// 实际上，我们只需要对事件中的y坐标离散化
discrete_y.push_back(ev.y);
}
}
sort(discrete_y.begin(), discrete_y.end());
discrete_y.erase(unique(discrete_y.begin(), discrete_y.end()), discrete_y.end());
solve_cdq(0, events.size() - 1);
events.clear();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k >> q;
for (int i = 1; i <= n; ++i) {
cin >> points[i].x >> points[i].y;
}
int query_count = 0;
// 初始状态
for (int i = 1; i <= n; ++i) {
add_point_events(i, 0, 1);
}
for (int i = 0; i < q; ++i) {
int type;
cin >> type;
if (type == 1) {
query_count++;
} else if (type == 2) {
long long u;
cin >> u;
process_batch();
k *= u;
// k可能会变得非常大，超过坐标范围，此时所有点对都满足
// 题目数据范围暗示k不会无限增长，这里可以加个上限
k = min(k, 400005LL);
// 为新的k值准备初始事件
for (int j = 1; j <= n; ++j) {
add_point_events(j, query_count, 1);
}
} else {
int u;
long long new_x, new_y;
cin >> u >> new_x >> new_y;
// 删除旧点
add_point_events(u, query_count, -1);
// 更新坐标
points[u] = {new_x, new_y};
// 添加新点
add_point_events(u, query_count, 1);
}
}
process_batch();
// 计算最终答案
for (int i = 1; i <= query_count; ++i) {
query_results[i] += query_results[i - 1];
}
for (int i = 1; i <= query_count; ++i) {
// S = query_results[i]
// 答案是 (S - n) / 2
cout << (query_results[i] - n) / 2 << "\n";
}
return 0;
}复杂度分析
时间复杂度:
- 我们将操作按 的变化分批。设共有 个批次（即
op=2的次数 + 1）。 - 对于每个批次，假设有 个事件（包括初始点、点修改等）。 的规模是 ，其中 是批次内的操作数。
- CDQ分治的复杂度是 ，因为递归深度是 ，每层需要排序和扫描，成本是 。
- 在最坏情况下，所有操作都在一个批次内，复杂度为 。
- 我们将操作按 的变化分批。设共有 个批次（即
空间复杂度:
- 主要空间开销来自于存储所有事件的
events数组，以及用于离散化的discrete_y数组。它们的数量级与总操作数 相关。树状数组的大小也与此相关。
- 主要空间开销来自于存储所有事件的
知识点总结
- 曼哈顿距离与切比雪夫距离的转换: 通过旋转坐标系 （即 ），可以将曼哈顿距离问题转化为切比雪夫距离问题，将复杂的
|dx|+|dy|约束变为简单的max(|dx'|,|dy'|)矩形约束。 - 离线处理: 遇到棘手的全局修改（如本题的
k变化），可以考虑将操作分批，对每个批次统一处理，这是一种典型的离线思想。 - CDQ分治: 解决多维（通常是三维）偏序/数点问题的强大工具。核心思想是分而治之，将高维问题降维处理。本题中，我们将一个动态的二维数点问题看作一个静态的三维数点问题（时间，x'，y'），但通过巧妙的事件建模，用一个二维CDQ解决了它。
- 二维矩形查询的分解: 使用类似二维前缀和的原理（容斥原理），将一个矩形查询分解为四个单点的前缀区域查询，方便用数据结构处理。
- 扫描线与树状数组: 在CDQ分治的合并步骤中，常用“扫描线+数据结构”的模式来计算跨区间的贡献。这里我们用扫描线扫过一维（），用树状数组维护另一维（）。
希望这篇题解能帮助你完全理解这道题的精髓！继续加油哦，指挥官！喵~