PerfectPan
;

HDUOJ 6191 对称数

August 01, 2018

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

题意:略。

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

#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;
}

Yiming Pan

Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github

Cannot load comments. Please check you network.