[BZOJ5361]/[HDU6291]对称数

题目大意：

一个\(n(n\le2\times10^5)\)个结点的树，每个结点有一个权值\(a_i(a_i\le2\times10^5)\)，\(m(m\le2\times10^5)\)次询问，每次询问\((u,v)\)路径上最小的出现偶数次的数。

思路：

对每个权值随机一个unsigned long long作为一个新的权值，树上主席树维护区间异或和。

询问时在主席树上二分即可。

源代码：

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<algorithm>

inline int getint() {

    register char ch;

    while(!isdigit(ch=getchar()));

    register int x=ch^'0';

    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

    return x;

}

typedef unsigned long long uint64;

const int N=2e5+1,logN=40;

int a[N],v[N],anc[N][logN],dep[N],mex;

uint64 w[N],hsum[N];

std::vector<int> e[N];

inline void add_edge(const int &u,const int &v) {

    e[u].push_back(v);

    e[v].push_back(u);

}

inline int lg2(const float &x) {

    return ((unsigned&)x>>23&255)-127;

}

class FotileTree {

    #define mid ((b+e)>>1)

    private:

        struct Node {

            uint64 val;

            int left,right;

        };

        Node node[N*logN];

        int sz,new_node(const int &p) {

            node[++sz]=node[p];

            return sz;

        }

    public:

        void reset() {

            sz=0;

        }

        int root[N];

        void insert(int &p,const int &b,const int &e,const int &x) {

            p=new_node(p);

            node[p].val^=w[v[x]];

            if(b==e) return;

            if(x<=mid) insert(node[p].left,b,mid,x);

            if(x>mid) insert(node[p].right,mid+1,e,x);

        }

        int query(const int &p,const int &q,const int &r,const int &s,const int &b,const int &e) const {

            if((node[p].val^node[q].val^node[r].val^node[s].val)==(hsum[e]^hsum[b-1])) return mex;

            if(b==e) return v[b];

            const int tmp=query(node[p].left,node[q].left,node[r].left,node[s].left,b,mid);

            if(tmp==mex) return query(node[p].right,node[q].right,node[r].right,node[s].right,mid+1,e);

            return tmp;

        }

    #undef mid

};

FotileTree t;

void dfs(const int &x,const int &par) {

    anc[x][0]=par;

    dep[x]=dep[par]+1;

    for(register int i=1;i<=lg2(dep[x]);i++) {

        anc[x][i]=anc[anc[x][i-1]][i-1];

    }

    const int p=std::lower_bound(&v[1],&v[v[0]]+1,a[x])-v;

    t.insert(t.root[x]=t.root[par],1,v[0],p);

    for(unsigned i=0;i<e[x].size();i++) {

        const int &y=e[x][i];

        if(y==par) continue;

        dfs(y,x);

    }

}

inline int get_lca(int x,int y) {

    if(dep[x]<dep[y]) std::swap(x,y);

    for(register int i=lg2(dep[x]-dep[y]);i>=0;i--) {

        if(dep[anc[x][i]]>=dep[y]) x=anc[x][i];

    }

    if(x==y) return x;

    for(register int i=lg2(dep[x]);i>=0;i--) {

        if(anc[x][i]!=anc[y][i]) {

            x=anc[x][i];

            y=anc[y][i];

        }

    }

    return anc[x][0];

}

inline int query(const int &x,const int &y) {

    const int lca=get_lca(x,y);

    return std::min(t.query(t.root[x],t.root[y],t.root[lca],t.root[anc[lca][0]],1,v[0]),mex);

}

int main() {

    srand(19961993);

    for(register int T=getint();T;T--) {

        memset(anc,0,sizeof anc);

        const int n=getint(),m=getint();

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

            v[i]=a[i]=getint();

            while(w[a[i]]==0) {

                w[a[i]]=(uint64)rand()*rand()*rand();

            }

        }

        std::sort(&v[1],&v[n]+1);

        v[0]=std::unique(&v[1],&v[n]+1)-v-1;

        for(register int i=mex=1;i<=v[0];i++) {

            hsum[i]=hsum[i-1]^w[v[i]];

            if(v[i]==mex) mex++;

        }

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

            add_edge(getint(),getint());

        }

        dfs(1,0);

        for(register int i=0;i<m;i++) {

            printf("%d\n",query(getint(),getint()));

        }

        t.reset();

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

            e[i].clear();

        }

    }

    return 0;

}

巴特西

[BZOJ5361]/[HDU6291]对称数

[BZOJ5361]/[HDU6291]对称数

题目大意：

思路：

源代码：

最新文章

热门文章