题解 P7502 「HMOI R1」不知道是啥的垃圾题

Miko35 · 2021-04-07 11:49:54 · 题解

验题人来水一水题解。

异或，比大小，很容易想到 Trie 树。但是这题插入的是二元组，很难用普通的 01trie 进行维护。

既然是二元组，有一个初步的想法是，将 Trie 开成四叉的，其中令 ch_{x,i,j}(i,j \in \{ 0,1 \}) 表示：节点 x 内的二元组 (x,y) 中，x 二进制下一位为 i，y 二进制下一位为 j 的二元组集合。也就是说，插入的向量的第 i 位是 (x,y) 取第 i 位形成的二元组。

比如从高到低插入插入二元组 (1,3)：

这样就可以像 01trie 一样实现异或比大小，也就是：将 x \operatorname{xor} a=1,y \operatorname{xor} b=0 的节点计入答案，然后分别递归 x \operatorname{xor} a=y \operatorname{xor} b=0/1 的点。

显然这样不是很对，因为每一层要递归两个节点，一次操作总共涉及的节点数到了 O(M) 级别。

观察可知，一个点能被递归下去，当且仅当在这一位 x \operatorname{xor} a=y \operatorname{xor} b，而这个可以写成 x \operatorname{xor} y=a \operatorname{xor} b，左边只跟 x,y 有关。这样插入时只需要保留两个儿子：下一位 x \operatorname{xor} y=1 和 =0 的，查询时只需要根据 a \operatorname{xor} b 的取值决定往哪边走即可。

依然要在每个节点处记录下一位 (x,y)=(0/1,0/1) 的二元组个数，这样才可以在递归时统计答案。

良心题，代码真心不长。

#include<bits/stdc++.h>
#define g(a) ((a)>>d&1)
long long x,y;
int m,o,c,S[1<<23][2][2],r,h[1<<23][2];
void s(int& r,int d){
    if(~d)S[r?r:r=++c][g(x)][g(y)]+=3-o*2,s(h[r][g(x^y)],d-1);
}
int q(int r,int d){
    return r&&~d?S[r][!g(x)][g(y)]+q(h[r][g(x^y)],d-1):0;
}
int main(){
    std::cin>>m;
    while(m--)std::cin>>o>>x>>y,o^3?s(r,60):void(printf("%d\n",q(r,60)));
}