Problem
初始有一个空集合 \(S\)。需要维护两种操作：
- 向集合中加入一个数 \(w\)，保证在这之前 \(w \notin S\)。
- 给定 \(w\)，找到两个不同的数 \(i,j\in S\)，使得 \((i+x)\oplus(j+x)\) 的值最小， \(x\in [1,w]\)。其中 \(\oplus\) 表示按位异或。
来自 ZR 某年省选十连的 day5？
Solution
Task 1.
考虑对于 \(0\le a\le b\le c\) 有 \(a\oplus c \ge \min (a\oplus b,b\oplus c)\)。
因为对于 \(a\oplus c\) 的最高位的 \(1\)，\(a\oplus b\) 和 \(b\oplus c\) 中应该恰好有一个这位为 \(0\)，所以得证。
Task 2.
然后其次另外的就是 \(b-a\le b \oplus a\)。
显然，由异或的性质所以可以将其看作不进位的加法或者不补位的减法，所以得证。
然后我们用两个基本的 Task 来解决这个问题。
对于 Task 1.
可以知道 \(S\) 中的数一定只有相邻的数才有贡献。
对于 Task 2.
对于一个数对 \((i,j)\) 其实只有一些必要的 \(x\) 使得 \((i+x)\oplus(j+x)\) 最小，实际上就是考虑以 \(x\) 制出 \(\mathrm{f}(x)=(i+x)\oplus(j+x)\) 这样一个函数，记录一个集合 \(X\) 为必要的 \(x\) 的集合，有 \(\forall x'<x:\mathrm{f}(x')> f(x)\)。
实际上应该有 \(X\sube \{x|x=\min\{a|\mathrm{P}(a)\}\}\)，其中 \(\mathrm{P}(a):2^k\mid (i+a) \lor 2^k \mid (j+a),k\in \N\)。
说人话就是 \(x\) 一定要满足一个条件就是 \((i+x)\) 或 \((j+x)\) 的后 \(k\) 位为 \(0\)，且 \(x\) 是满足前者的最小值。
考虑 \((i+x)\) 的后 \(k\) 位为 \(0\)。
这时如果 \(x\) 增加，\(j+x\) 产生了进位向 \(k+1\) 位，那么就考虑到 \(j+x\) 和后 \(k+1\) 位为 \(0\) 的情况。
否则考虑后 \(k\) 位，增加前的贡献应该是 \((j+x)\) 后 \(k\) 位，设为 \(y\)，增加后贡献应该是 \((x+\Delta x) \oplus (j+(x+\Delta x))\) 的后 \(k\) 位，设为 \(y'\)。根据 Task 2. 应该有 \(y\le y'\) 。
所以可以用 \(\textrm{set}\) 来维护相邻的贡献以及二元组 \((x,(i+x) \oplus(j+x))\)。
然后就完了，剩下的应该都会。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read (){
int p = 0;
char c = getchar ();
while (c < '0' || c > '9')
c = getchar ();
while (c >= '0' && c <= '9'){
p = (p << 1) + (p << 3) + c - 48;
c = getchar ();
}
return p;
}
inline void write (int x){
if (x > 9)
write (x / 10);
putchar (x % 10 + 48);
}
int V, Q;
set < int > pot;
set < pair < int , int > > plt;
void Push (int x, int v){
auto it = plt.lower_bound (make_pair (x, 0));
auto rit = it;
if (rit != plt.begin ()){
-- rit;
if ((*rit).second <= v)
return ;
}
for (auto iit = it;it != plt.end ();){
++ iit;
if ((*it).second >= v)
plt.erase (it ++);
else
break;
it = iit;
}
if (it == plt.end () || (*it).first > x)
plt.insert (make_pair (x, v));
}
void Add (int x, int y){
Push (0, x ^ y);
for (int i = 0, a;i <= V;++ i){
a = (1ll << i) - (x & ((1ll << i) - 1ll));
Push (a, (x + a) ^ (y + a));
}
for (int i = 0, a;i <= V;++ i){
a = (1ll << i) - (y & ((1ll << i) - 1ll));
Push (a, (x + a) ^ (y + a));
}
}
signed main (){
V = read (), Q = read ();
for (int T = 1, opt, w;T <= Q;++ T){
opt = read (), w = read ();
if (opt == 2){
auto it = plt.lower_bound (make_pair (w + 1, 0));
-- it;
write ((*it).second), puts ("");
}
if (opt == 1){
auto it = pot.upper_bound (w);
if (it != pot.end ())
Add (w, *it);
if (it != pot.begin ()){
-- it;
Add (*it, w);
}
pot.insert (w);
}
}
return 0;
}