题解：P11209 『STA - R8』小熊游景点 II

· · 题解

这道题目能想到正解还是不容易的。
首先看数据范围：1 \le n,m \le 5 \times 10^5。如果暴力做肯定超时。

前置知识

字典树，模板题传送门。

具体过程

那么看到题目中的异或运算，我们可以试着往字典树的方向来思考题目。
建一个只有 0 和 1 的字典树，对于每个结点都有一个标记 x，表示从根结点到这个结点所形成的二进制数 k 能满足 x 个 i 使得 (a_i\oplus k)\le b_i，其中 \oplus 是按位异或。

完成定义后，就开始来思考，进行分类讨论：

  1. 如果在二进制下这一位的 b_i 是 1，这个时候异或的结果可以有两种情况，如果异或的结果为 0，则一定满足条件，k 的这一位就要等于 a_i 的这一位，这时就不用往下走了，直接给那个结点的标记 + 1。如果异或的结果为 1，则还需要考虑后面的位数，于是就继续往下走。需要注意的是，如果到了最后一位，异或的结果为 1 时也能满足条件，也要给更新标记。
  2. 如果在二进制下这一位的 b_i 是 0，这个时候异或的结果只能有一种情况，那就是 0，这个时候 k 的这一位等于 a_i 的这一位。然后还需要继续往下走，同样要特判最后一位。

这样就基本解决完了。在计算答案时，把 k 的二进制在字典树上走一遍，把一路上的标记都相加即可。

代码

理解透了代码就很好写。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, MX = 15000005;
int n, T, trie[MX][3], a[N], b[N], Q, lst, jd[MX], cnt;
void ins(int num, int num2){
    int now = 0;
    for(int i = 29;i >= 0;i--){
        int zh = ((num >> i) & 1), zh2 = ((num2 >> i) & 1);
        if(zh2){
            //如果没有这个结点就新建一个结点
            if(trie[now][zh] == 0) trie[now][zh] = ++cnt; 
            jd[trie[now][zh]]++;
            if(trie[now][zh ^ 1] == 0) trie[now][zh ^ 1] = ++cnt;
            now = trie[now][zh ^ 1];
            if(i == 0) jd[now]++;//特判i==0 
        } else{
            if(trie[now][zh] == 0) trie[now][zh] = ++cnt;
            now = trie[now][zh];
            if(i == 0) jd[now]++;
        }
    }
}
int fin(int num){
    int now = 0, ans = 0;
    for(int i = 29;i >= 0;i--){
        int zh = ((num >> i) & 1);
        if(trie[now][zh] == 0) break;
        now = trie[now][zh];
        //把k的二进制在字典树上走一遍，把所有标记相加
        ans += jd[now];
    }
    return ans;
}
int main(){
    scanf("%d%d%d", &T, &n, &Q);
    for(int i = 1;i <= n;i++) scanf("%d", &a[i]);
    for(int i = 1;i <= n;i++){
        scanf("%d", &b[i]);
        ins(a[i], b[i]);
    }
    while(Q--){
        int k;
        scanf("%d", &k);
        k = k ^ (lst * T);
        int da = fin(k);
        printf("%d\n", da);
        lst = da;
    }
    return 0;
}