题解 P7264 【Mirror】
囧仙
2021-01-10 22:45:51
由于出题人提供的题解的证明不甚清晰，于是打算自己写一篇题解谈一谈想法。
> $\verb!upd 2021.1.10 23:14!$ 修正了一些笔误。管理审核太快了还没来得及勘误 $\verb!qwq!$
## 题目大意
- 一个无穷大的矩阵，坐标为 $(x,y)$ 的格子可以通过当且仅当 $x\operatorname{and} y=0$ ，其中 $\operatorname{and}$ 是二进制下的与操作。
- 现在矩阵上有 $n$ 个位置 $(x_i,y_i)$ 为炸弹。询问从 $(s_x,s_y)$ 到 $(t_x,t_y)$ 的**最短路径**上有哪些炸弹。
## 题解
通过大眼观察法，我们能够从题目中所给的 $64\times 64$ 的矩阵图上观察到这样两个很重要的结论：
- 这张图形成了一个树形结构。也就是说，两点之间的路径**唯一确定**。
- 假使满足 $x>0,y>0$ 的点 $(x,y)$ 可以通过，那么 $(x-1,y)$ 和 $(x,y-1)$ 中**有且仅有**一个点可以通过。
我们先考虑第二个结论，因为根据这个结论可以反过来证明第一个结论。
事实上，假使 $x>0,y>0$ 的 $(x,y)$ 可以通过，那么 $x\operatorname{and} y=0$ 。于是对于不存在某个二进制位，使得 $x,y$ 的这一位同时相同。怎么样考虑 $x-1$ 后它的二进制值的变化呢？考虑 $x,y$ 的最右侧的为 $1$ 的位，因为减 $1$ 操作只会影响到这一位以及更低位的二进制值。不妨设 $x$ 最右侧的位是 $p$ ， $y$ 最右侧的位是 $q$ ，其所对应的二进制位是 $2^p$ 和 $2^q$ 。显然， $p\neq q$ （不然 $x,y$ 的与值就不为 $0$ 了） 那么要么 $p<q$ ，要么 $p>q$ 。
当 $p<q$ 时， $2^p-1$ 的末尾 $p-1$ 位全部都是 $1$ ，并且不会影响到 $x$ 的 $p+1$ 位以后的数位。但是由于 $p<q$ ，于是这部分 $1$ 和 $y$ 的与值仍然为 $0$ ，于是 $(x-1) \operatorname{and} y=0$ ，于是 $(x-1,y)$ **可以通过**。同时， $2^q-1$ 的末尾 $q-1$ 位全部都是 $1$ ，由于 $p<q$ ，于是此时 $x \operatorname{and} (y-1)\neq 1$ ，也就是 $(x,y-1)$ **不可通过**。
当 $p>q$ 时如法炮制，可以发现 $(x-1,y)$ 与 $(x,y-1)$ 中有且仅有一个可以通过。我们不妨将其与其左侧/上侧那个可达的点连边。
考虑第 $0$ 行和第 $0$ 列的数字。显然，除了 $(0,0)$ ，都可以向左侧或者上侧的点连边。于是所有点联通，并且边数是总点数 $-1$ 。这时已经满足**整张图是树形结构**这样的结论了。
下面考虑如何构造解法。事实上，在刚刚的论证过程中，我们提到了最低的为 $1$ 的位。我们可以用 $\operatorname{lowbit}$ 函数进行求值，其中 $\operatorname{lowbit}(x)$ 表示 $x$ 的最低位的 $1$ 对应的二进制数的值，并且 $\operatorname{lowbit}(x)=x\operatorname{and}(-x)$ （树状数组中也经常用到这个结论）。由于路径唯一，并且每个点只能向上或者向左走，我们可以考虑每个点每次走的时候**最远走多少**。
我们先找出 $(s_x,s_y),(t_x,t_y)$ 如果分别向左上角走，最终会走到哪里（不妨设为 $(p_x,p_y)$ ） 。观察可得该图为一个分形，并且每一个子正方形的第 $0$ 行第 $0$ 列都是可通过的位置。于是从小到大枚举这个子正方形的边长 $2^k$ 。我们能够通过 $\left\lfloor\dfrac{s_x}{2^k}\right\rfloor,\left\lfloor\dfrac{s_y}{2^k}\right\rfloor$ 计算出 $(s_x,s_y)$ 所在的这个正方形是第几排第几个的正方形。只要判断起点和终点是否在同一个正方形中就行了，可以计算出 $(p_x,p_y)$ 。由于是一个子图，我们可以将刚刚出现过的**所有坐标**（包括起点终点和炸弹坐标）向左平移 $p_x$ 、向上平移 $p_y$ ，于是起点和终点最终应当在第 $0$ 行或者第 $0$ 列会合了。
假设当前点在 $(x,y)$ ，满足 $x\neq 0$ 且 $y \neq 0$ 。考虑每次向左或者向上走尽可能远的距离。同样，我们求出 $x,y$ 的最低位 $p,q$ 。不妨设 $p<q$ ，那么该点可以不停向左走。什么时候这个点要改变方向了呢？
不妨举个例子：
$$\begin{aligned}
x&=554_{(10)}&=1000101010_{(2)} \cr
y&=336_{(10)}&=0101010000_{(2)} \cr
\end{aligned}$$
显然，由于 $p<q$ ，我们要不断减去 $x$ 的值，也就是向上走。可以发现，对于 $x$ 的后 $q$ 位，无论它的值如何，与上 $y$ 都是 $0$ 。那么也就是说，我们要不断减去这后 $q$ 位，直到他们全部为 $0$ 。
$$\begin{aligned}
x&=544_{(10)}&=1000100000_{(2)} \cr
y&=336_{(10)}&=0101010000_{(2)} \cr
\end{aligned}$$
此时 $p,q$ 的大小关系就对调了。于是我们应当向左走了。这一部分一共花费了 $554-544=10$ 步。
可以证明，全过程中走的步数不会超过 $\log_2(x+y)$ 。因为每走一段路，$x$ 或 $y$ 的 $\operatorname{lowbit}$ 值至少加上 $1$ 。
然后这条路就被我们拆分成了 $\log_2(x+y)$ 个线段。分别对 $(s_x,s_y),(t_x,t_y)$ 执行这些操作，直到他们的横坐标或者列坐标到达了 $0$ 。
考虑最后一步。事实上我们要考虑他们会不会在 $(0,0)$ 相遇，而这取决于他们是否在同一行或者同一列上了。这部分只需要判断一下，~~留给读者自几处理~~。
那么最后线段总数应该是 $\log_2v$ 级别的（ $v$ 是值域）。对于每个炸弹，枚举所有线段，判断这个炸弹是否在这条线段上。总复杂度 $\mathcal O(n\log v)$ 。由于不像题解中用到比较麻烦的递归，所以速度飞起，拿到了赛时最块。
## 参考代码
```cpp
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
const int MAXN =2e5+3,MAXM=500+3;
i64 n,X[MAXN],Y[MAXN],s1,s2,t1,t2,ans;
i64 A[MAXM],B[MAXM],C[MAXM],p;
i64 P[MAXM],Q[MAXM],R[MAXM],q;
void del(i64 &x,i64 &y){
while(x!=0&&y!=0){
if(!((x-1)&y)){i64 t=y&-y,l=x&(t-1); A[++p]=y,B[p]=x-l,C[p]=x,x-=l,ans+=l;}
else {i64 t=x&-x,l=y&(t-1); P[++q]=x,Q[q]=y-l,R[q]=y,y-=l,ans+=l;}
}
}
i64 qread(){
i64 w=1,c,ret;
while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
return ret*w;
}
int main(){
n=qread(); up(1,n,i) X[i]=qread(),Y[i]=qread();
s1=qread(),s2=qread(),t1=qread(),t2=qread();
up(1,60,i){
i64 l=1ll<<i,a1=s1/l,a2=s2/l,b1=t1/l,b2=t2/l,p1,p2;
if(a1==b1&&a2==b2){
p1=a1*l,p2=a2*l,s1-=p1,s2-=p2,t1-=p1,t2-=p2;
up(1,n,j) X[j]-=p1,Y[j]-=p2; break;
}
}
del(s1,s2),del(t1,t2);
printf("%lld\n",ans+llabs(s1-t1)+llabs(s2-t2));
P[++q]=min(s1,t1),Q[q]=min(s2,t2),R[q]=max(s2,t2);
A[++p]=min(s2,t2),B[p]=min(s1,t1),C[p]=max(s1,t1);
up(1,n,i){
bool f=0;
up(1,p,j) if(Y[i]==A[j]&&X[i]>=B[j]&&X[i]<=C[j]) f=true;
up(1,q,j) if(X[i]==P[j]&&Y[i]>=Q[j]&&Y[i]<=R[j]) f=true;
putchar(f?'1':'0');
}
return 0;
}
```