[cf1479D]Odd Mineral Resource

先考虑判定是否有解，注意到无解即每一个数都出现偶数次，根据异或的性质，只需要随机$V_{i}$，假设$u$到$v$路径上所有节点构成集合$S$，若$\bigoplus_{x\in S,l\le a_{x}\le r}V_{a_{x}}=0$即无解

考虑如何快速计算上述值，根据异或的自反性，对其差分，也即统计一个节点到根路径上的权值异或，建立线段树，并在其父亲的基础上可持久化即可

更进一步的，在这个线段树上二分即可得到答案（即先判定每一段是否为0，再在其中二分）

时间复杂度为$o(n\log n)$，即可通过

下面来分析概率，假设$V_{i}$的随机范围为$[0,V)$（其中$V$为2的幂次），考虑答案错误的概率——

考虑一次询问中，求得异或为0但实际存在出现奇数次权值的概率，即$\frac{1}{V}$

总共询问$o(q\log n)$次，可以估计概率为$\frac{q\log n}{V}$，当$V\sim 2^{64}$即足够高

（另外注意随机时，如果是选择若干个数相乘，需要判定最终结果不为0）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 300005

 4 #define ull unsigned long long

 5 #define mid (l+r>>1)

 6 struct Edge{

 7     int nex,to;

 8 }edge[N<<1];

 9 int V,E,n,q,x,y,l,r,z,zz,head[N],dep[N],rt[N],a[N],f[N][21],ls[N*20],rs[N*20];

10 ull R[N],sum[N*20];

11 int New(int k){

12     sum[++V]=sum[k];

13     ls[V]=ls[k];

14     rs[V]=rs[k];

15     return V;

16 }

17 void add(int x,int y){

18     edge[E].nex=head[x];

19     edge[E].to=y;

20     head[x]=E++;

21 }

22 int lca(int x,int y){

23     if (dep[x]<dep[y])swap(x,y);

24     for(int i=20;i>=0;i--)

25         if (dep[f[x][i]]>=dep[y])x=f[x][i];

26     if (x==y)return x;

27     for(int i=20;i>=0;i--)

28         if (f[x][i]!=f[y][i]){

29             x=f[x][i];

30             y=f[y][i];

31         }

32     return f[x][0];

33 }

34 void update(int &k,int l,int r,int x,ull y){

35     k=New(k);

36     sum[k]^=y;

37     if (l==r)return;

38     if (x<=mid)update(ls[k],l,mid,x,y);

39     else update(rs[k],mid+1,r,x,y);

40 }

41 int query(int k1,int k2,int k3,int k4,int l,int r,int x,int y){

42     if ((l>y)||(x>r))return -1;

43     if ((x<=l)&&(r<=y)){

44         if (!(sum[k1]^sum[k2]^sum[k3]^sum[k4]))return -1;

45     }

46     if (l==r)return l;

47     int ans=query(ls[k1],ls[k2],ls[k3],ls[k4],l,mid,x,y);

48     if (ans>=0)return ans;

49     return query(rs[k1],rs[k2],rs[k3],rs[k4],mid+1,r,x,y);

50 }

51 void dfs(int k,int fa,int s){

52     dep[k]=s;

53     f[k][0]=fa;

54     for(int i=1;i<=20;i++)f[k][i]=f[f[k][i-1]][i-1];

55     rt[k]=rt[fa];

56     update(rt[k],1,n,a[k],R[a[k]]);

57     for(int i=head[k];i!=-1;i=edge[i].nex)

58         if (edge[i].to!=fa)dfs(edge[i].to,k,s+1);

59 }

60 int main(){

61     srand(time(0));

62     scanf("%d%d",&n,&q);

63     for(int i=1;i<=n;i++)scanf("%d",&a[i]);

64     for(int i=1;i<=n;i++)

65         while (!R[i])R[i]=(ull)rand()*(ull)rand()*(ull)rand()*(ull)rand()*(ull)rand();

66     memset(head,-1,sizeof(head));

67     for(int i=1;i<n;i++){

68         scanf("%d%d",&x,&y);

69         add(x,y);

70         add(y,x);

71     }

72     dfs(1,0,1);

73     for(int i=1;i<=q;i++){

74         scanf("%d%d%d%d",&x,&y,&l,&r);

75         z=lca(x,y),zz=f[z][0];

76         printf("%d\n",query(rt[x],rt[y],rt[z],rt[zz],1,n,l,r));

77     }

78 }

巴特西

[cf1479D]Odd Mineral Resource

最新文章

热门文章