HDU5589 Tree【分块 01字典树】

HDU5589 Tree

题意：

给出一棵\(N\)个点的树，每条边有边权，每次询问下标为\([L,R]\)区间内的点能选出多少点对，点对之间的路径上的边权异或和大于\(M\)

题解：

对于两点\(u,v\)之间的路径上的边权的异或和，可以转化为根到点\(u\)的路径上异或和与根到点\(v\)的路径上异或和的异或和，所以可以与处理出根到各个点的路径边权异或和

接下来就变成了一个序列上的问题了，每次询问区间\([L,R]\)之间的点有多少对的异或和大于\(M\)

然后就可以用莫队来处理，为了能快速加值和删值还有查询，而且是异或的操作，这里选择用\(01\)字典树来做

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 5e4+7;

typedef long long int LL;

int n,m,q,w[MAXN];

LL ret[MAXN],ans;

struct Trie{

    int tot,ch[MAXN<<4][2],cnt[MAXN<<4];

    void clear(){

        for(int i = 1; i <= tot; i++) ch[i][0] = ch[i][1] = cnt[i] = 0;

        tot = 1;

    }

    void insert(int x, int now = 1){

        for(int i = 19; i >= 0; i--){

            if(!ch[now][(x>>i)&1]) ch[now][(x>>i)&1] = ++tot;

            cnt[now = ch[now][(x>>i)&1]]++;

        }

    }

    void erase(int x, int now = 1){

        for(int i = 19; i >= 0; i--) cnt[now = ch[now][(x>>i)&1]]--;

    }

    int query(int x){

        int ret = 0, now = 1;

        for(int i = 19; i >= 0 and now; i--){

            int bm = ((m>>i)&1);

            int bx = ((x>>i)&1);

            if(!bm) ret += cnt[ch[now][bx^1]], now = ch[now][bx];

            else now = ch[now][bx^1];

        }

        return ret;

    }

}trie;

struct Query{ int l, r, id; } Q[MAXN];

vector<pair<int,int>> G[MAXN];

void dfs(int u, int par){

    for(auto e : G[u]) if(e.first!=par){

        w[e.first] = w[u] ^ e.second;

        dfs(e.first,u);

    }

}

void inc(int x){

    ans += trie.query(x);

    trie.insert(x);

}

void dec(int x){

    trie.erase(x);

    ans -= trie.query(x);

}

void solve(){

    for(int i = 1; i <= n; i++) G[i].clear();

    for(int i = 1; i < n; i++){

        int u, v, wt;

        scanf("%d %d %d",&u,&v,&wt);

        G[u].push_back(make_pair(v,wt)); G[v].push_back(make_pair(u,wt));

    }

    dfs(1,0); trie.clear();

    for(int i = 1; i <= q; i++) scanf("%d %d",&Q[i].l,&Q[i].r), Q[i].id = i;

    int sqt = sqrt(n);

    sort(Q+1,Q+1+q,[&sqt](const Query &lhs, const Query &rhs){

        return lhs.l / sqt == rhs.l / sqt ? lhs.r < rhs.r : lhs.l / sqt < rhs.l / sqt;

    });

    int L = 1, R = 0;

    ans = 0;

    for(int i = 1; i <= q; i++){

        while(L>Q[i].l) inc(w[--L]);

        while(R<Q[i].r) inc(w[++R]);

        while(L<Q[i].l) dec(w[L++]);

        while(R>Q[i].r) dec(w[R--]);

        ret[Q[i].id] = ans;

    }

    for(int i = 1; i <= q; i++) printf("%I64d\n",ret[i]);

}

int main(){

    while(scanf("%d %d %d",&n,&m,&q)!=EOF) solve();

    return 0;

}

巴特西

HDU5589 Tree【分块 01字典树】

题意：

题解：

最新文章

热门文章