Aly_

题意简述

• 一行 $n$ 对数，第 $i$ 对数为权值对 $<a_i,b_i>$。
• 回答 $q$ 个询问 $<l_j,r_j,c_j,d_j>$，询问的是在 $l_j$ 到 $r_j$ 内所有数对中满足 $a_i\operatorname{xor} c_j\leq\min(b_i,d_j)$ 的数对个数。
• $1\leq n,q\leq 10^5$，$1\leq l_j\leq r_j\leq n$，$0\leq a_i, b_i, c_j$, $d_j\leq 2^{24} - 1$。

解法

​ 先考虑一个询问怎么求。

​ 看到异或就知道大概是要建 0-1 trie 的。对于一个询问，分 $b_i\geq d_j$ 和 $b_i<d_j$ 两种情况考虑。

​ 对于 $b_i\geq d_j$ 的情况，要求即为 $a_i\operatorname{xor} c_j\leq d_j$ ，以 $a_i$ 为权值建出序列的 0-1 trie。

​ 令 $c_j$ 从高位往低位走，对于一个节点（假设 $c_j$ 当前位为 $0$）有 $0$ 和 $1$ 两个儿子：若 $d_j$ 当前位为 $1$，则 $0$ 儿子及其子树一定可行，$1$ 儿子可能可行，向 $1$ 递归；反之 $1$ 儿子一定不可行，向 $0$ 递归。这一部分是 0-1 trie 经典问题，不再赘述。

​ 对于 $b_i< d_j$ 的情况，要求即为 $a_i\operatorname{xor} c_j\leq b_i$ 。

​ 分析一下各种情况，这里还是假设 $c_j$ 当前位为 $0$：

• $a_i$ 当前位为 $0$，$b_i$ 当前位为 $0$：可能可行，需向下递归。
• $a_i$ 当前位为 $0$，$b_i$ 当前位为 $1$：一定可行，子树全部可行。
• $a_i$ 当前位为 $1$，$b_i$ 当前位为 $0$：一定不可行，子树全部不可行。
• $a_i$ 当前位为 $1$，$b_i$ 当前位为 $1$：可能可行，需向下递归。

​ 观察发现：当 $a_i\operatorname{xor}b_i=0$ 时需要向下递归，否则要么全可行，要么全不可行。

​ 对 $c_j$ 当前位为 $1$ 的情况分析类似。

​ 以 $a_i\operatorname{xor}b_i$ 为权值建出序列的 0-1 trie，再在每个节点记录其子树内 $a_i=0$ 和 $1$ 的数的个数。查询时令 $c_j$ 从高位往低位走，按上面的讨论做即可。

​ 再考虑原问题。按 $b_i,d_j$ 排序，顺着扫一遍，分块维护两组 trie 树：一组是关于 $b_i\geq d_j$ 的，另一组是关于 $b_i< d_j$ 的，扫的时候在 trie 上动态加点删点即可。

​ 设块长为 $B$，值域为 $A$，时间复杂度 $O(n\log A+Q(\frac{n}{B}\log A+B))$。$n,Q$ 同级，理论取 $B=\sqrt{n\log n}$，实践中设 $B=2000\sim 3000$ 时最优。空间 $O(n\log A)$。

​ 较小的常数使得分块做法的通过成为可能。

​ CDQ 分治之类的做法（似乎）也可以类似地套用。按 $b_i,d_j$ 排序，分治时左区间对右区间的贡献即所有 $b_i$ 的插入（$b_i< d_j$ 部分的 trie 树上）和删除（ $b_i\geq d_j$ 的 trie 树上）。其它题解里有这方面的详细讲解。

​ 不济的话把分块（时间被卡）和树套树（空间被卡）结合一下把块长调大一点也能过。

​ 放一下关键位置的源代码（$b_i< d_j$ 部分的 trie 树建立与查询）：

void trieadd1(int u,int aa,int bb,int np){
	if(!np)return;
	int ng=(((aa^bb)&(1<<(np-1)))>>(np-1));
	if(!son[u][ng])son[u][ng]=++pb;
	dq[son[u][ng]][(aa&(1<<np-1))>>(np-1)]++;
	trieadd1(son[u][ng],aa,bb,np-1);
}
int triereq1(int u,int x,int np){
	if(!u)return 0;
	if(!np)return dq[u][0]+dq[u][1];
	int ng=((x&(1<<(np-1)))>>(np-1));
	return triereq1(son[u][ng],x,np-1)+dq[son[u][ng^1]][ng];
}