一些最近刷到的好题，还有一些没见过的处理方式。
定义 \(f(x)=(x\oplus a)-b\)，其中 \(a,b\) 是给定的参数。
给定 \(n\) 个变量，\(x_1,x_2,x_3,\dots,x_n\)，给出 \(q\) 组询问，对于每组询问，给定 \(a,b\)，请你输出一个 \(i\)，满足 \(i\in [1,n)\)，且有 \(f(x_i)\times f(x_{i+1})\le 0\)，如果无解则输出 \(-1\)，如果有多组解输出任意一个即可。
很好的题目，根本不知道要用什么算法。思考过 Trie 树，但是感觉没有什么用。
看了题解，这东西竟然能二分？？？？
有个很重要的结论：
如果 \(\max f(x)\times \min f(x)\le0\)，那么肯定有解。
看上去非常不对，不是要相邻才行吗？
实际上无解的情况当且仅当所有 \(f(x)\) 同号，上面那个式子成立了就说明有正有负或者有零。
然后就可以对这个东西二分了。
找到 \(\max f(x)\) 和 \(\min f(x)\) 的位置，这个东西可以用 Trie 树搞。
不妨把它们的位置设为 \([l,r]\)，那么 \([l,r]\) 长度为 \(2\) 的时候 \(l\) 就是答案了。
考虑不断去缩小这个区间。取 \(mid=\lfloor\frac{l+r}{2}\rfloor\)，\(f(x_l)\times f(x_{mid})\le 0\) 和 \(f(x_{mid})\times f(x_r)\le 0\) 一定至少有一个成立，哪个成立往哪边缩小就好了。
代码的实现并不困难，时间复杂度 \(\mathcal O(q(\log V+\log n))\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e6+10;
int n,q,tot;
int trie[N][2],id[N],a[N];
void add(int x,int y)
{
int now=0;
for(int i=30;i>=0;i--)
{
int c=(x>>i)&1;
if(!trie[now][c])trie[now][c]=++tot;
now=trie[now][c];
}
id[now]=y;
}
int find(int x,int op)
{
int now=0;
for(int i=30;i>=0;i--)
{
int c=(x>>i)&1^op;
if(trie[now][c])now=trie[now][c];
else now=trie[now][!c];
}
return id[now];
}
bool check(int x,int y,int l,int r)
{
return ((a[l]^x)-y)*((a[r]^x)-y)<=0;
}
signed main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
add(a[i],i);
}
while(q--)
{
int x,y;
scanf("%lld%lld",&x,&y);
int l=find(x,0),r=find(x,1);
if(l>r)swap(l,r);
if(!check(x,y,l,r))
{
puts("-1");
continue;
}
while(l+1<r)
{
int mid=(l+r)/2;
if(!check(x,y,l,mid))l=mid;
else r=mid;
}
cout<<r-1<<endl;
}
return 0;
}