自动搬运

查看原文

来自洛谷，原作者为

	vzcx_host vzcx 系列第一站

搬运于2025-08-24 22:44:22，当前版本为作者最后更新于2023-09-06 08:38:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在本题解中，约定 $k=2^{13}=8192$，所有数组下标均从 $0$ 开始编号。

题意简述与分析

现有一个长度为 $k$ 的数组 $sgn$，满足 $sgn_i\in\{1,-1\}$，且已知 $sgn_{k-1}=1,sgn_{k-2}=-1$。

对于一个长度为 $k$ 的 01 串 $S$，定义 $f(S)=\sum_{0\le i<k}[S_i=1]sgn_i 2^i$，$g(x)$ 为 $f(x)$ 的反函数。

二进制加法的法则是“逢 $2$ 进 $1$”，由定义可知，对于任意两个长度为 $k$ 的 01 串 $S,T$，$g(f(S)+f(T))$ 的值就是对 $S$ 和 $T$ 做“逢 $2$ 进 $1$ 或 $-1$”的“二进制加法”后得出的结果，也可以发现，题目中的加法运算与这里的加法完全一致。（讲的不够清楚，但这一段非常重要）

同样，由于加法运算的存在，证明了 $f(x)$ 存在反函数 $g(x)$。

现每次询问要求给出两个长度为 $k$ 的 01 串 $S,T$，交互库会返回 $g(f(S)+f(T))$，用尽量少的询问套出 $sgn$ 数组。

题目补充：三个 Subtask 的 $LIMIT$ 分别为 $8200,5550,4096$。

Solution

定义 $R=g(f(S)+f(T))$。

若 $f(S)+f(T)$ 的第 $i$ 位发生进位，且之后的所有位均为 $0$，则 $R$ 的第 $i$ 位后会出现一段连续的 $1$，其中最高位的 $1$ 所在位与第 $i$ 位同号，中间的 $1$ 所在位与第 $i$ 位异号。

对每一位分开询问即可，最大询问次数为 $8190$，可得 $10$ 分。

在上一个做法中，我们让每次询问恰好发生一次进位，这样会大幅度浪费询问次数，考虑多进程询问。

考虑分块，一次进位要么只会影响该位所在的块内的部分，要么会发生“跨块”。如果某一个块发生“跨块”，那么这个块内的所有位会被全部做完，所以“跨块”最多会发生 $\sqrt{k}$ 次，当跨块发生时停止处理后面的块即可。

询问上限 $2\sqrt{k}\le 182$，可以通过本题。

以上为标算的做法，接下来，我们要开启快乐的踩标之旅！

反过来考虑，如果我们令 $S=11111111\dots 1111,T=00000000\dots 0001$，得到的 $R$ 必然为一段 $1$ 后跟一段 $0$，其中最高位的 $0$ 与最低位异号，其余的 $0$ 与最低位同号。我们还可以发现，更高位的 $1$ 还可以供我们多线程询问。

因此，对于当前要解决的区间 $(l\sim r,d)$，其中 $r+1\sim d-1$ 与 $r$ 同号，$d$ 与 $r$ 异号，我们可以对 $mid$ 做一次单点询问，对得到的最高位的 $0$ 所在位 $p$ 再做一次单点询问，设第二次询问得到的最高位的 $0$ 在第 $q$ 位，我们可以确定 $mid\sim p-1$ 与 $mid$ 同号，$p\sim q-1$ 与 $mid$ 异号，$q$ 与 $mid$ 同号。同时，原区间被分为了两个区间 $(l\sim mid,p)$ 和 $(q\sim r,d)$，子区间依然满足原区间的性质，由于中间的异号位充足，两个子区间不会对对方产生影响，多个不交的区间同时进行即可。

询问上限 $2\log_2 k = 26$，完成一般踩标。

我们想想当询问利用率达到极限会发生什么。

令 $S=T=11111111\dots 1111$，对于 $R$ 某一位，若该位与下一位同号，则下一位会进 $1$，下一位会正常进位；若该位与下一位异号，则下一位会退 $1$，下一位不会进位，带来的影响就是再下一位必定为 $0$。

因此，若 $R$ 的第 $i$ 位为 $0$，则它的上一位和上上位异号，它和上一位的关系不知道，对不知道的关系做一次统一询问即可。由于两个询问位之间必定有一组异号关系，按最原始的方法询问不会出现互相影响的问题。

询问上限 $2\times 1 = 2$，完成爆踩标算。