双机巡检 题解

1. 状态为什么可以压缩

记环上距离为

$$d(x,y)=\min(|x-y|,n-|x-y|).$$

在一个只有一个要求点 $p$ 的阶段结束后，可以认为：一台机器人停在 $p$，另一台机器人没有进行与当前要求无关的移动。因为如果另一台机器人提前走了一段路，这段移动总可以推迟到它下一次真正执行任务时再完成；由最短路的三角不等式，这样做不会增加总代价。

所以，若从最近一个含两个要求点的阶段之后开始，只处理了一段单点阶段，那么状态可以写成

$$F_x=\text{当前要求点已有一台机器人，另一台在 }x\text{ 时的最小代价}.$$

机器人没有编号。状态中的“当前要求点上的机器人”和“另一台机器人”只描述此刻的位置关系，并不是为两台实体机器人永久编号。

2. 单点阶段的转移

设上一个单点要求为 $p$，新要求为 $y$。

有两种选择：

1. 仍由位于 $p$ 的机器人前往 $y$。此时对每个 $x$ 都有

   $$F'_x=F_x+d(p,y).$$

2. 由位于 $x$ 的另一台机器人前往 $y$。此时原来位于 $p$ 的机器人变成“另一台”，因此只会更新状态 $p$：

   $$F'_p\gets\min\left(F'_p,\min_x\{F_x+d(x,y)\}\right).$$

于是一次转移只需要支持三种操作：

• 全部状态加上同一个数；
• 查询 $\min_x\{F_x+d(x,y)\}$；
• 对单个位置做取最小值。

3. 两点阶段如何衔接

含两个要求点的阶段会把两台机器人的位置完全固定为一个无序对 $\{u,v\}$。

若上一个阶段已经固定在 $\{a,b\}$，转移代价就是两种匹配方式中的较小值：

$$\min\bigl(d(a,u)+d(b,v),\ d(a,v)+d(b,u)\bigr).$$

若它接在一段单点阶段之后，最后一个单点要求为 $p$，则答案增加

$$\min\left( d(p,u)+\min_x\{F_x+d(x,v)\}, d(p,v)+\min_x\{F_x+d(x,u)\} \right).$$

随后旧的 $F$ 状态全部清空，重新从固定位置 $\{u,v\}$ 开始。

一段单点阶段的第一个要求为 $p$，其前面的固定位置为 $\{a,b\}$ 时，初始状态是

$$F_a\gets d(b,p),\qquad F_b\gets d(a,p).$$

若两次更新落在同一位置，只需保留较小值。

4. 环形距离查询

用一个全局懒加量 $A$ 表示所有状态共同增加的代价，在线段树中保存

$$B_x=F_x-A.$$

这样全体加法只需修改 $A$，单点更新仍然是一次 chmin。现在需要查询

$$A+\min_x\{B_x+d(x,y)\}.$$

先看数轴上的绝对值。对固定查询点 $y$，有

$$\min_x\{B_x+|x-y|\} =\min\left( y+\min_{x\le y}(B_x-x), -y+\min_{x\ge y}(B_x+x) \right).$$

因此维护两棵区间最小值线段树，分别保存 $B_x-x$ 与 $B_x+x$，即可在 $O(\log n)$ 时间内查询。

为了处理环，把每个位置 $x$ 同时复制到 $x$ 和 $x+n$，并分别在 $y$、$y+n$ 上做数轴查询，取较小值。这样所有跨过边 $(n,1)$ 的最短路径也会被包含。

清空一段单点状态时，不需要重建整棵线段树。记录本段中真正被修改过的叶子，只恢复这些叶子即可。每次单点更新至多新产生常数个叶子，因此所有清空操作的总复杂度仍是 $O(q\log n)$。

5. 正确性证明

引理 1

存在一个最优方案，使每个单点阶段结束时，除负责覆盖当前要求点的机器人外，另一台机器人不做与当前要求无关的提前移动。

证明： 若另一台机器人在本阶段提前移动，而这段移动直到之后某个阶段才产生作用，就把它推迟到那个阶段之前执行。移动的起点、终点不变，总代价不变；若中间路线发生合并，最短路的三角不等式还可能使代价下降。反复处理即可得到所述方案。$\square$

引理 2

给定单点阶段前的全部状态 $F_x$，第 2 节的两类转移恰好得到下一阶段的全部最优状态。

证明： 根据引理 1，新要求 $y$ 必须由两台机器人之一完成。若由原来位于当前要求点 $p$ 的机器人完成，另一台仍在 $x$，得到第一类转移；若由原来位于 $x$ 的机器人完成，原来位于 $p$ 的机器人成为另一台，得到第二类转移。两类情况不漏解，且每个候选代价都对应一个合法移动方案。$\square$

引理 3

第 3 节的公式正确处理所有两点阶段。

证明： 两个不同要求点必须分别由两台机器人占据。由于机器人无区别，只有两种对应方式，枚举并取最小值即为最优。两点阶段结束后，位置无序对被唯一确定，因此可以丢弃此前的其余状态。$\square$

引理 4

复制坐标后的两棵线段树返回 $\min_x\{B_x+d(x,y)\}$。

证明： 把 $x$ 复制为 $x$ 与 $x+n$，把查询点复制为 $y$ 与 $y+n$，四种数轴距离的最小值正是环上顺、逆时针两条路径长度的较小值。对任意一次数轴查询，按 $x\le y$ 和 $x\ge y$ 拆开绝对值后，恰好分别由 $B_x-x$ 与 $B_x+x$ 的区间最小值给出。$\square$

定理

算法输出完成全部巡检阶段的最小总代价。

证明： 初始固定位置是 $\{1,n\}$。按阶段归纳：单点阶段由引理 2 保持全部状态的最优值；两点阶段由引理 3 得到准确最优代价并形成新的固定状态；引理 4 保证数据结构计算的每次距离最小值与转移式完全一致。最后若停在单点阶段，只需在所有 $F_x$ 中取最小值。因此输出即全局最优解。$\square$

6. 复杂度分析

线段树含 $2n$ 个位置。每个阶段只进行常数次查询或单点修改，所有延迟清空的修改次数也是 $O(q)$。

• 时间复杂度：$O((n+q)\log n)$；
• 空间复杂度：$O(n)$。

7. 子任务做法

子任务	可行做法	复杂度
$1$	令两台机器人有临时编号，对所有位置对做状态 DP	$O(qn^3)$
$2$	使用本题的 $F_x$ 状态，但每次线性扫描所有 $x$ 求距离最小值	$O(qn)$
$3$	每个阶段都固定两个位置，只比较两种匹配	$O(q)$
$4$	两台机器人都只需考虑端点 $1,n$，维护常数个位置状态
$5$	只有一个单点块，使用环形距离变换线段树，不需要清空	$O((n+q)\log n)$
$6$	单点块 DP、环形距离变换线段树和按修改叶子清空

8. 参考程序

#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <vector>

class DistanceStructure {
public:
    explicit DistanceStructure(int point_count)
        : point_count_(point_count), doubled_count_(2 * point_count) {
        size_ = 1;
        while (size_ < doubled_count_) {
            size_ <<= 1;
        }
        min_minus_.assign(2 * size_, infinity());
        min_plus_.assign(2 * size_, infinity());
    }

    void chmin_point(int position, std::int64_t value) {
        chmin_doubled(position, value);
        chmin_doubled(position + point_count_, value);
        minimum_value_ = std::min(minimum_value_, value);
    }

    std::int64_t query_cycle(int position) const {
        return std::min(query_line(position), query_line(position + point_count_));
    }

    std::int64_t minimum_value() const {
        return minimum_value_;
    }

    void clear() {
        for (int position : touched_) {
            assign_doubled(position, infinity());
        }
        touched_.clear();
        minimum_value_ = infinity();
    }

private:
    static constexpr std::int64_t infinity() {
        return std::numeric_limits<std::int64_t>::max() / 4;
    }

    void chmin_doubled(int position, std::int64_t value) {
        int index = size_ + position - 1;
        const std::int64_t old_value = min_minus_[index] >= infinity() / 2
            ? infinity()
            : min_minus_[index] + position;
        if (value >= old_value) {
            return;
        }
        if (old_value >= infinity() / 2) {
            touched_.push_back(position);
        }
        min_minus_[index] = value - position;
        min_plus_[index] = value + position;
        pull(index >> 1);
    }

    void assign_doubled(int position, std::int64_t value) {
        int index = size_ + position - 1;
        if (value >= infinity() / 2) {
            min_minus_[index] = infinity();
            min_plus_[index] = infinity();
        } else {
            min_minus_[index] = value - position;
            min_plus_[index] = value + position;
        }
        pull(index >> 1);
    }

    void pull(int index) {
        while (index > 0) {
            min_minus_[index] = std::min(min_minus_[index << 1], min_minus_[index << 1 | 1]);
            min_plus_[index] = std::min(min_plus_[index << 1], min_plus_[index << 1 | 1]);
            index >>= 1;
        }
    }

    std::int64_t range_min(const std::vector<std::int64_t>& tree,
                           int left, int right) const {
        std::int64_t result = infinity();
        int l = size_ + left - 1;
        int r = size_ + right - 1;
        while (l <= r) {
            if (l & 1) {
                result = std::min(result, tree[l++]);
            }
            if (!(r & 1)) {
                result = std::min(result, tree[r--]);
            }
            l >>= 1;
            r >>= 1;
        }
        return result;
    }

    std::int64_t query_line(int position) const {
        const std::int64_t from_left =
            range_min(min_minus_, 1, position) + position;
        const std::int64_t from_right =
            range_min(min_plus_, position, doubled_count_) - position;
        return std::min(from_left, from_right);
    }

    int point_count_;
    int doubled_count_;
    int size_;
    std::vector<std::int64_t> min_minus_;
    std::vector<std::int64_t> min_plus_;
    std::vector<int> touched_;
    std::int64_t minimum_value_ = infinity();
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    if (!(std::cin >> n >> q)) {
        return 0;
    }
    auto distance = [n](int x, int y) -> std::int64_t {
        const int direct = std::abs(x - y);
        return std::min(direct, n - direct);
    };

    DistanceStructure structure(n);
    bool in_single_block = false;
    int fixed_first = 1;
    int fixed_second = n;
    int last_request = 1;
    std::int64_t fixed_cost = 0;
    std::int64_t block_add = 0;

    for (int stage = 0; stage < q; ++stage) {
        int count, first;
        std::cin >> count >> first;
        if (count == 1) {
            if (!in_single_block) {
                structure.chmin_point(fixed_first, distance(fixed_second, first));
                structure.chmin_point(fixed_second, distance(fixed_first, first));
                block_add = 0;
                last_request = first;
                in_single_block = true;
            } else {
                const std::int64_t switch_robot =
                    block_add + structure.query_cycle(first);
                block_add += distance(last_request, first);
                structure.chmin_point(last_request, switch_robot - block_add);
                last_request = first;
            }
        } else {
            int second;
            std::cin >> second;
            if (!in_single_block) {
                fixed_cost += std::min(
                    distance(fixed_first, first) + distance(fixed_second, second),
                    distance(fixed_first, second) + distance(fixed_second, first));
            } else {
                const std::int64_t move_to_first =
                    distance(last_request, first) + block_add + structure.query_cycle(second);
                const std::int64_t move_to_second =
                    distance(last_request, second) + block_add + structure.query_cycle(first);
                fixed_cost += std::min(move_to_first, move_to_second);
                structure.clear();
                block_add = 0;
                in_single_block = false;
            }
            fixed_first = first;
            fixed_second = second;
        }
    }

    if (in_single_block) {
        fixed_cost += block_add + structure.minimum_value();
    }
    std::cout << fixed_cost << '\n';
    return 0;
}