题意:
给出一棵树,每次询问两点之间是否存在一个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); } }