1479D.Odd Mineral Resource(可持久化线段树+树上差分+随机算法)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了1479D.Odd Mineral Resource(可持久化线段树+树上差分+随机算法),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2631字,纯文字阅读大概需要4分钟。
内容图文
题意:
给出一棵树,每次询问两点之间是否存在一个l到r之间的数出现奇数次,找到这个数。
题解:
询问是否出现奇数次,用可持久化线段树套树上差分维护异或和。
找到这个数,不套随机数一直wa5,看了官方题解,里面有证明套随机数求解这个问题可以做到大概率正确。woc真的好难。
#include<bits/stdc++.h> using namespace std; const int maxn=3e5+100; const int M=maxn*80; mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int T[maxn],lson[M],rson[M],c[M],sum[M],tot,n,q,a[maxn],h[maxn],father[30][maxn],Rd[maxn]; vector<int> g[maxn]; int build (int l,int r) { int root=tot++; c[root]=0; sum[root]=0; if (l!=r) { int mid=(l+r)>>1; lson[root]=build(l,mid); rson[root]=build(mid+1,r); } return root; } int up (int root,int p,int v) { int newRoot=tot++; int tmp=newRoot; int l=1,r=n; c[newRoot]=c[root]+v; sum[newRoot]=sum[root]^Rd[p]; while (l<r) { int mid=(l+r)>>1; if (p<=mid) { lson[newRoot]=tot++; rson[newRoot]=rson[root]; newRoot=lson[newRoot]; root=lson[root]; r=mid; } else { rson[newRoot]=tot++; lson[newRoot]=lson[root]; newRoot=rson[newRoot]; root=rson[root]; l=mid+1; } c[newRoot]=c[root]+v; sum[newRoot]=sum[root]^Rd[p]; } return tmp; } int cal (int x,int y,int lca,int flca,int l,int r,int L,int R) { if (l==r) return l; int mid=(l+r)>>1; if (sum[lson[x]]^sum[lson[y]]^sum[lson[lca]]^sum[lson[flca]]) return cal(lson[x],lson[y],lson[lca],lson[flca],l,mid,L,R); else return cal(rson[x],rson[y],rson[lca],rson[flca],mid+1,r,L,R); } int query (int x,int y,int lca,int flca,int l,int r,int L,int R) { //L R表示要查询的区间 if (l>=L&&r<=R) { if (sum[x]^sum[y]^sum[lca]^sum[flca]) return cal(x,y,lca,flca,l,r,L,R); else return -1; } int mid=(l+r)>>1; int ans=-1; if (L<=mid) ans=query(lson[x],lson[y],lson[lca],lson[flca],l,mid,L,R); if (ans!=-1) return ans; if (R>mid) ans=query(rson[x],rson[y],rson[lca],rson[flca],mid+1,r,L,R); return ans; } void dfs (int x) { T[x]=up(T[father[0][x]],a[x],1); for (int y:g[x]) { if (y==father[0][x]) continue; father[0][y]=x; h[y]=h[x]+1; dfs(y); } } int lca (int x,int y) { if (h[x]<h[y]) swap(x,y); for (int i=20;i>=0;i--) if (h[x]-h[y]>>i) x=father[i][x]; if (x==y) return x; for (int i=20;i>=0;i--) { if (father[i][x]!=father[i][y]) { x=father[i][x]; y=father[i][y]; } } return father[0][x]; } int main () { scanf("%d%d",&n,&q); for (int i=1;i<=n;i++) scanf("%d",a+i); for (int i=1;i<=n;i++) Rd[i]=rd(); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } T[0]=build(1,n); dfs(1); for (int i=1;i<=20;i++) for (int j=1;j<=n;j++) father[i][j]=father[i-1][father[i-1][j]]; while (q--) { int u,v,l,r; scanf("%d%d%d%d",&u,&v,&l,&r); int Lca=lca(u,v); int ans=query(T[u],T[v],T[Lca],T[father[0][Lca]],1,n,l,r); printf("%d\n",ans); } }
内容总结
以上是互联网集市为您收集整理的1479D.Odd Mineral Resource(可持久化线段树+树上差分+随机算法)全部内容,希望文章能够帮你解决1479D.Odd Mineral Resource(可持久化线段树+树上差分+随机算法)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。