关键思路

将移动过程转化为矩形覆盖问题：

初始有 N 个矩形

每个移动命令 (矩形I, 方向V, 距离D) 会产生 D 个新矩形

最终需要回答 Q 个查询：点 P 被多少个矩形覆盖

算法框架

1. 矩形表示

对于从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的矩形移动：

如果沿水平或垂直方向移动：轨迹形成的长条矩形可以直接计算

如果沿对角线方向移动：轨迹形成的矩形是起点矩形和终点矩形的外包矩形

2. 扫描线算法

由于直接枚举所有矩形会超时，使用扫描线 + 线段树： cpp

// 伪代码框架 vector solve() { // 1. 收集所有矩形 vector all_rects = 初始矩形; for (每个移动命令) { for (移动的每一步) { 计算当前步的矩形位置; all_rects.add(该矩形); } }

// 2. 离散化坐标
vector<int> xs, ys;
for (auto rect : all_rects) {
    xs.add(rect.x1); xs.add(rect.x2);
    ys.add(rect.y1); ys.add(rect.y2);
}
排序去重(xs); 排序去重(ys);

// 3. 构建扫描线事件
vector<Event> events;
for (auto rect : all_rects) {
    events.add({rect.x1, rect.y1, rect.y2, +1});  // 进入
    events.add({rect.x2, rect.y1, rect.y2, -1});  // 离开
}
按x坐标排序(events);

// 4. 扫描线处理
SegmentTree tree(ys.size());  // 支持区间加、单点查询的线段树
vector<Answer> answers;

int event_idx = 0;
for (每个离散化后的x坐标) {
    // 处理所有在当前x位置的事件
    while (events[event_idx].x == current_x) {
        tree.update(events[event_idx].y1, events[event_idx].y2, events[event_idx].type);
        event_idx++;
    }
    
    // 回答所有x坐标为current_x的查询
    for (每个查询点p，且p.x == current_x) {
        answers[p] = tree.query(p.y);
    }
}

return answers;

}

复杂度分析

时间：O((N + M \cdot D + Q) \log Y)，其中 Y 是y坐标范围

空间：O(N + M \cdot D) 存储所有矩形

优化方向

对于大数据（$N,M,Q \leq 2.5\times 10^5$）：

不显式生成所有矩形，而是直接计算每个移动产生的矩形范围

使用更紧凑的数据结构表示移动轨迹

对于对角线移动，可以分解为x方向和y方向的独立影响

核心难点

正确计算移动轨迹形成的矩形

处理坐标离散化

实现高效的范围更新、点查询线段树