差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:contest:cf_700_div._1 [2021/02/09 20:49]
jxm2001 [题解 1]
+++ 2020-2021:teams:legal_string:jxm2001:contest:cf_700_div._1 [2021/02/10 11:29] (当前版本)
jxm2001
@@ 行 228: / 行 228: @@
 	_rep(i,1,m)
 	enter(ans[i]);
+	return 0;
+}
+</code>
+</hidden>
+==== 题解 2 ====
+首先给 $1\sim n$ 每个权值一个 $\text{unsigned long long}$ 范围内的 $\text{hash}$ 值。
+于是 $v_1,v_2,\cdots v_k$ 中有某个数出现奇数次近似等效为 $\text{hash}(v_1)\oplus \text{hash}(v_2)\cdots\oplus\text{hash}(v_k)\neq 0$。
+定义 $f(u,l,r)$ 表示从根节点到 $u$ 所有权值在 $[l,r]$ 的权值的 $\text{hash}$ 值的异或和。
+于是询问等效于查询 $f(u,l,r)\oplus f(v,l,r)\oplus f(\text{lca}(u,v),l,r)\oplus f(\text{p}(\text{lca}(u,v)),l,r)$ 是否等于 $0$。
+主席树维护根节点到每个节点的权值区间异或和，查询时先找到权值区间内不为 $0$ 的范围，然后再 $\log n$ 找到答案即可。
+时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=3e5+5;
+mt19937_64 mt(time(NULL));
+struct Node{
+	int ch[2];
+	unsigned long long val;
+}node[MAXN*40];
+#define lch(k) node[node[k].ch[0]]
+#define rch(k) node[node[k].ch[1]]
+#define f(k1,k2,k3,k4) (node[k1].val^node[k2].val^node[k3].val^node[k4].val)
+int root[MAXN],node_cnt;
+int nodecopy(int k){
+	node[++node_cnt]=node[k];
+	return node_cnt;
+}
+void update(int &k,int p,int lef,int rig,int pos,unsigned long long v){
+	k=nodecopy(p);
+	node[k].val^=v;
+	if(lef==rig)return;
+	int mid=lef+rig>>1;
+	if(mid>=pos)
+	update(node[k].ch[0],node[p].ch[0],lef,mid,pos,v);
+	else
+	update(node[k].ch[1],node[p].ch[1],mid+1,rig,pos,v);
+}
+int query_ans(int k1,int k2,int k3,int k4,int lef,int rig){
+	int mid=lef+rig>>1;
+	if(lef==rig)return mid;
+	if(f(node[k1].ch[0],node[k2].ch[0],node[k3].ch[0],node[k4].ch[0])!=0)
+	return query_ans(node[k1].ch[0],node[k2].ch[0],node[k3].ch[0],node[k4].ch[0],lef,mid);
+	else
+	return query_ans(node[k1].ch[1],node[k2].ch[1],node[k3].ch[1],node[k4].ch[1],mid+1,rig);
+}
+int query(int k1,int k2,int k3,int k4,int lef,int rig,int ql,int qr){
+	if(ql<=lef&&rig<=qr){
+		if(f(k1,k2,k3,k4)==0)
+		return -1;
+		else
+		return query_ans(k1,k2,k3,k4,lef,rig);
+	}
+	int mid=lef+rig>>1;
+	if(mid>=qr)
+	return query(node[k1].ch[0],node[k2].ch[0],node[k3].ch[0],node[k4].ch[0],lef,mid,ql,qr);
+	else if(mid<ql)
+	return query(node[k1].ch[1],node[k2].ch[1],node[k3].ch[1],node[k4].ch[1],mid+1,rig,ql,qr);
+	int temp=query(node[k1].ch[0],node[k2].ch[0],node[k3].ch[0],node[k4].ch[0],lef,mid,ql,qr);
+	if(temp!=-1)return temp;
+	return query(node[k1].ch[1],node[k2].ch[1],node[k3].ch[1],node[k4].ch[1],mid+1,rig,ql,qr);
+}
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+namespace LCA{
+	int d[MAXN],sz[MAXN],f[MAXN];
+	int h_son[MAXN],mson[MAXN],p[MAXN];
+	void dfs_1(int u,int fa,int depth){
+		sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0;
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(v==fa)
+			continue;
+			dfs_1(v,u,depth+1);
+			sz[u]+=sz[v];
+			if(sz[v]>mson[u])
+			h_son[u]=v,mson[u]=sz[v];
+		}
+	}
+	void dfs_2(int u,int top){
+		p[u]=top;
+		if(mson[u])dfs_2(h_son[u],top);
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(v==f[u]||v==h_son[u])
+			continue;
+			dfs_2(v,v);
+		}
+	}
+	void init(int root){dfs_1(root,0,0);dfs_2(root,root);}
+	int query(int u,int v){
+		while(p[u]!=p[v]){
+			if(d[p[u]]<d[p[v]])swap(u,v);
+			u=f[p[u]];
+		}
+		return d[u]<d[v]?u:v;
+	}
+};
+int a[MAXN],n;
+unsigned long long h[MAXN];
+void dfs(int u,int fa){
+	update(root[u],root[fa],1,n,a[u],h[a[u]]);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs(v,u);
+	}
+}
+int main()
+{
+	n=read_int();
+	int q=read_int();
+	_rep(i,1,n)a[i]=read_int();
+	_rep(i,1,n)h[i]=mt();
+	_for(i,1,n){
+		int u=read_int(),v=read_int();
+		Insert(u,v);
+		Insert(v,u);
+	}
+	LCA::init(1);
+	dfs(1,0);
+	while(q--){
+		int u=read_int(),v=read_int(),ql=read_int(),qr=read_int(),p=LCA::query(u,v);
+		enter(query(root[u],root[v],root[p],root[LCA::f[p]],1,n,ql,qr));
+	}
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具