LC1938-查询最大基因差

1938. 查询最大基因差

离线 + \(Trie\)

建树后\(dfs\)，每访问一个节点 \(v\)，就插入 \(Trie\) ，并回答v的所有询问，然后将 \(v\) 从 \(Trie\)中删去。

using PII = pair;
const int N = 1e5 + 10;
int son[N * 18][2], idx, cnt[N * 18];
class Solution {
public:
    vectorans;
    vector>q;
    void insert(int x){
        int p = 0;
        for(int i = 17; i >= 0; --i){
            int u = x >> i & 1;
            if(!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
            cnt[p] ++;
        }
    }
    int query(int x){
        int res = 0, p = 0;
        for(int i = 17; i >= 0; --i){
            int u = x >> i & 1;
            if(cnt[son[p][!u]]) res += 1 << i, p = son[p][!u];
            else p = son[p][u];
        }
        return res;
    }
    void remove(int x){
        int p = 0;
        for(int i = 17; i >= 0; --i){
            int u = x >> i & 1;
            if(!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
            cnt[p] --;
        }
    }
    void dfs(vector> &G, int root){
        insert(root);
        for(int i = 0; i < q[root].size(); ++i)
            ans[q[root][i].first] = max(ans[q[root][i].first], query(q[root][i].second));
        for(auto& e : G[root]) dfs(G, e);
        remove(root);
    }
    vector maxGeneticDifference(vector& parents, vector>& queries) {
        idx = 0;
        memset(son, 0, sizeof son);
        memset(cnt, 0, sizeof cnt);
        int n = parents.size(), root = -1;
        ans.resize(queries.size());
        q.resize(N + 1);
        vector>G(n + 1);
        for(int i = 0; i < n; ++i)  // 建图
            if(parents[i] == -1) root = i;
            else G[parents[i]].push_back(i);
        for(int i = 0; i < queries.size(); ++i) q[queries[i][0]].push_back({i ,queries[i][1]});//离线存储询问
        dfs(G, root);
        return ans;
    }
};