[题解] [Mivik Round nurture] Mirror

一个无穷的地图，行列从 0 开始标号。$(i,j)$ 可以通过当且仅当 $(i\&j)=0$。同时地图中还有 $n$ 个炸弹。现在给出两个格子，保证可以通过，问从一个格子走到另一个格子至少需要走多少步，且在步数最少的情况下至少需要拆除哪些炸弹。

$1\le n\le 2\cdot 10^5$，$0\le x,y\le 10^{18}$

题目链接

---

思路

Subtask 1

由于可以直走，两个点之间要走多少格就是它们的曼哈顿距离了，然后中间需要拆除的障碍物直接判一下就好了。

Subtask 2

如果你善于观察，那么你会发现当起点位于 $(0,0)$ 时，两个点之间要走多少格依旧等于他们的曼哈顿距离。为什么呢？

我们注意到时刻都必须有 $x\&y=0$，初始时是满足条件的，那么我们考虑每次取出 $(x|y)$ 的 lowbit，然后把这一位走掉，一直这样直到走到 $(0,0)$，我们的总路径是 $(x+y)$。举个例子，假设 $(x,y)=(4,3)$，那么我们先写出二进制：

x: 100

y: 011

然后 lowbit 是 $y$ 的 1，所以我们从 $(4,3)$ 走到 $(4,2)$，变成了：

x: 100

y: 010

lowbit 是 $y$ 的 2，所以我们从 $(4,2)$ 走到 $(4,0)$，变成了：

x: 100

y: 000

然后直接走到 $(0,0)$ 就可以了。容易发现最短的路径是唯一的，因为如果你减少的那一维不是 lowbit 所在的那一维的话，那么必定会产生一堆 1，然后这堆 1 就会和 lowbit 所在的那一维位与不为 0 了，不合法。

综上，我们模拟一下上面那个过程就好了。

mivik.h

// Mivik 2021.1.6
#include <mivik.h>

#include <algorithm>
#include <list>

using std::list;

MI cin;

typedef long long qe;

const int N = 200005;

struct point { qe x, y; };
template<> struct Q<point> { inline void operator()(MI &r, point &t) {
	r > t.x > t.y;
} };
int N;
point st, en, bar[N];
bool vis[N];
list<int> rem; // 还没被处理的障碍物
int main() {
	cin > n;
	for (int i = 1; i <= n; ++i) {
		cin > bar[i];
		rem.push_back(i);
	}
	cin > st > en;
	if (st.x || st.y) {
		cout < "Orz\n";
		return 0;
	}
	auto &[x, y] = en;
	cout < (x + y) < endl;
	for (int i = 0; i < 60; ++i) { // 扫描 lowbit
		if ((x >> i) & 1) {
			const qe to = x & (x - 1);
			for (auto it = rem.begin(); it != rem.end(); ) {
				auto &p = bar[*it];
				if (p.y == y && to <= p.x && p.x <= x) {
					vis[*it] = 1;
					it = rem.erase(it);
				} else ++it;
			}
			x = to;
		} else if ((y >> i) & 1) {
			const qe to = y & (y - 1);
			for (auto it = rem.begin(); it != rem.end(); ) {
				auto &p = bar[*it];
				if (p.x == x && to <= p.y && p.y <= y) {
					vis[*it] = 1;
					it = rem.erase(it);
				} else ++it;
			}
			y = to;
		}
	}
	for (int i = 1; i <= n; ++i) cout < vis[i];
	cout < endl;
}

满分做法

实际上我们可以递归。每次把一个宽和高都为 $2^n$ 的迷宫（以 $(0,0)$ 为左上角）平均分成四个部分，即左上左下右上和右下，但右下是不能走的所以我们忽略。如果当前位置和终点在一个块就继续向下递归，否则我们使两个点都统一“走”到左上角那一块然后再递归到左上角。容易发现这样对答案是没有影响的。

根据我们在 Subtask 2 中得到的结论，在一个块内的点是可以用 $abs(x-\text{左上角x})+abs(y-\text{左上角y})$ 的步数走到左上角的，因此计算距离就容易了。但是障碍物的判断呢？

实际上我们只需要判断一下 $dist(st,p)+dist(p,en)$ 是否等于 $dist(st,en)$ 就好了，因为根据上面的说明我们知道两点间的最短路径只有一条。

时间复杂度 $O\left(\log^2(10^{18})n\right)$。但我的实现 稍 微 研究了一下二进制本质然后写了一个 $O(1)$ 判上面那个东西的函数，所以就少了个平方了。

代码

mivik.h

代码