P8988 Solution

· · 题解

在本题解中，约定 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，完成爆踩标算。