HDUOJ 6191 对称数

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=6291

题意:略。

思路:出现偶数次想到将一个数异或起来判断出现次数奇偶性,可以注意到出现偶数次最后结果即为0,且异或具有可以差分的性质,所以我们可以建立一棵树上主席树,权值线段树维护的是对应权值的异或和,每次查询的时候我们可以通过主席树的加加减减得到查询路径的权值线段树。然后接下来找最小的偶数就相当于找第一个叶子节点异或和为0的位置,直接在权值线段树上二分找就可以了,和找mex是一样的。因为直接异或对应的值肯定不对,可能出现1异或2等于3然后1,2代替掉3的情况,所以我们直接随机一个[0,2^{64})以内的权值就可以极大概率的避免冲突了。还有一个天坑就是可能[1,20000]都是出现奇数次,这时候答案是20001,所以我们要把权值线段树范围开到20001...因为这个坑了好久。

#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef unsigned long long ull;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=200000+10;
int T,n,m,i,u,v,cnt,root[N],a[N],son[N],dep[N],sz[N],fa[N],bel[N],ls[N*20],rs[N*20];
ull sum[N*20],val[N],pre[N];
vector<int>G[N];
inline ull Rand(){
    return (((ull)rand()%32768ll)<<45ll)+(((ull)rand()%32768ll)<<30ll)
          +(((ull)rand()%32768ll)<<15ll)+((ull)rand()%32768ll);
}
void ins(int&y,int last,int l,int r,int pos,ull v){
    sum[y=++cnt]=sum[last]^v;
    if (l==r) return;
    int mid=l+((r-l)>>1);
    ls[y]=ls[last],rs[y]=rs[last];
    if (pos<=mid) ins(ls[y],ls[last],l,mid,pos,v);
    else ins(rs[y],rs[last],mid+1,r,pos,v);
}
void dfs(int u,int f){
    fa[u]=f,sz[u]=1,son[u]=-1,dep[u]=dep[f]+1;
    ins(root[u],root[f],1,200001,a[u],val[a[u]]);
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        if (son[u]==-1 || sz[son[u]]<sz[v]) son[u]=v;
    }
}
void dfs2(int u,int f){
    bel[u]=f;
    if (son[u]==-1) return;
    dfs2(son[u],f);
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==fa[u] || v==son[u]) continue;
        dfs2(v,v);
    }
}
int lca(int u,int v){
    for (;bel[u]!=bel[v];dep[bel[u]]>dep[bel[v]]?u=fa[bel[u]]:v=fa[bel[v]]);
    return dep[u]>dep[v]?v:u;
}
int query(int A,int B,int C,int D,int l,int r){
    if (l==r) return l;
    int mid=l+((r-l)>>1);
    if ((sum[ls[A]]^sum[ls[B]]^sum[ls[C]]^sum[ls[D]])!=(pre[mid]^pre[l-1]))
        return query(ls[A],ls[B],ls[C],ls[D],l,mid);
    else
        return query(rs[A],rs[B],rs[C],rs[D],mid+1,r);
}
int main(){
    srand((unsigned)time(0));
    for (i=1;i<N;i++) val[i]=Rand();
    for (i=1;i<N;i++) pre[i]=pre[i-1]^val[i];
    for (read(T);T--;){
        read(n),read(m);
        for (cnt=0,i=1;i<=n;i++) G[i].clear();
        for (i=1;i<=n;i++) read(a[i]);
        for (i=1;i<n;i++){
            read(u),read(v);
            G[u].PB(v);
            G[v].PB(u);
        }
        dfs(1,0);
        dfs2(1,1);
        for (;m--;){
            read(u),read(v);
            int f=lca(u,v);
            printf("%d\n",query(root[u],root[v],root[f],root[fa[f]],1,200001));
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注