我永远喜欢数据结构。
给出 \(n\) 个二元组 \((a_i,b_i)\)，有 \(q\) 次询问，每次给出 \(l_i,r_i,c_i,d_i\)，求有多少个 \(j\) 满足 \(j\in[l_i,r_i]\) 且 \(a_j\oplus c_i\le \min\{b_j,d_i\}\)。
\(n,q\le 10^5\)，设值域为 \(V\)，\(|V|\le 2^{24}\)。
\(2.00\,\text{s}\,/\,256.00\,\text{MB}\)。
一句话题解：离线，拆 \(\min\)，考虑贡献。
我们知道线段树可以将一个区间拆成 \(\mathcal{O}(\log n)\) 个不交的节点，使得这些节点的并等于给定的区间。
于是我们考虑离线，在线段树上将每个询问拆成 \(\mathcal{O}(\log n)\) 个子区间，分别求解这些子区间的答案。
考虑对于线段树的一个节点 \([L,R]\)，求解挂在它上面的询问。将这些询问按照 \(d_i\) 从小到大排序，同时将节点内的二元组按照 \(b_j\) 从小到大排序。
对于一个询问，分成 \(b_j<d_i\) 和 \(b_j\ge d_i\) 两类二元组。不难发现排序后存在一个 \(\boldsymbol k\) 使得 \(\boldsymbol{k\in[L,R]}\) 且当 \(\boldsymbol{j\in[L,k)}\) 时，\(\boldsymbol{b_j<d_i}\)；当 \(\boldsymbol{j\in[k,R]}\) 时，\(\boldsymbol{b_j\ge d_i}\)。
即，两类二元组分别在一个连续区间内。
-
对于 \(b_j\ge d_i\) 的部分，\(\min\{b_j,d_i\}=d_i\)。
这部分较为平凡。就是求区间内有多少个数异或定值后不超过定值。使用 01 trie 维护，将区间内所有数加入 01 trie，统计根节点（即全局）的答案。
考虑一个子问题：统计以 \(u\) 为根的子树内的答案。维护每个点子树内部的答案。讨论 \(d_i\) 当前位是 \(0\) 还是 \(1\) 即可。若是 \(1\)，则另这一位取 \(0\) 的数都满足条件需要被统计。这样的数在当 \(u\) 的某个儿子内。维护一个 \(sz_u\) 表示以 \(u\) 为根的子树内，有多少个询问内的数。用 \(sz_u\) 以及递归儿子求解即可。
-
对于 \(b_j<d_i\) 的部分，\(\min\{b_j,d_i\}=b_j\)。
对于区间内的每个二元组，将其插入 01 trie，并考虑它会对哪些询问的 \(c_i\) 产生贡献。此时的 01 trie 是对于 \(c_i\) 维护的。
同样考虑这个二元组会被以 \(u\) 为根的子树内的哪些数统计。讨论 \(b_j\) 当前位是 \(0\) 还是 \(1\)。如果是 \(1\)，意味着另这一位为 \(0\) 的 \(c_i\) 都会统计到这个二元组。这样的 \(c_i\) 也在某个儿子的 \(u\) 的子树内。即子树内所有数的贡献 \(+1\)。此时 \(sz_u\) 数组变成懒标记，使得某个叶子的初始答案，加上它即其祖先的懒标记后，等于其在当前加入的二元组构成的集合中的答案。
对于一个询问，查询 \(c_i\) 的答案即可。由于初始空集合答案为 \(0\)，只需要统计根链上所有点的标记之和。
本质上是动态开点线段树。
由于实现的原因，01 trie 需要支持删除操作。因此我们不能简单地把空节点理解成不存在的节点。此处 01 trie 上的空节点定义为，仅当 \(\boldsymbol{sz_u=0}\) 时，\(\boldsymbol{u}\) 为空。注意那个是必要条件。这样我们不去计算空节点的原因不是因为其不存在，而是因为其没有贡献。
同样要再次强调这句话，本质上是动态开点线段树。
我们发现，由于排过序，若按顺序处理询问，\(\boldsymbol{k}\) 单调不降。
每次 \(k\) 移动时，将当前位置从第一类的 01 trie 中删除，加入第二类的 01 trie。这样在一个线段树节点内，一个二元组被操作的次数是 \(\mathcal{O}(1)\) 的。单次操作时间复杂度为 \(\mathcal{O}(\log |V|)\)，一个二元组会在 \(\mathcal{O}(\log n)\) 个线段树节点中被操作。
对于一个询问，拆分成了 \(\mathcal{O}(\log n)\) 段，一段查询的时间复杂度为 \(\mathcal{O}(\log |V|)\)。
所以，时间复杂度为 \(\mathcal{O}((n+q)\log n\log |V|)\)，空间复杂度为 \(\mathcal{O}((n+q)\log |V|)\)。
提交记录（\(\color{white}\colorbox{limegreen}{Accepted}\) \(\color{limegreen}\bf 100\)，\(\bf 8.00\,s\,/\,54.18\,MB\)） 代码
标签：01,log,trie,P7470,boldsymbol,2021,mathcal,节点,NOI From： https://www.cnblogs.com/MnZnOIerLzy/p/17864462.html