Posts CF1479Div1
Post
Cancel

CF1479Div1

D

给一棵树,有点权,$q(q\le 3\times10^5)$组询问$(u,v,l,r)$,问在$(u,v)$这条链上,是否存在权值在$l,r$之间,且出现奇数次的点,输出任意一个符合要求的权值,不存在输出-1

考场写了个俩log的,T掉了,呜呜。

给每个点权分配一个$[0,2^{64}-1]$内的随机数,这样子我们可以用一堆东西的异或判断是否存在出现奇数次的点。

每个节点维护一个线段树,下标表示点权范围,值是从当前点到根的异或值,我们用可持久化,每个点继承父亲节点的线段树来实现。

这样子,查询的时候只要在$u,v,lca(u,v),fa(lca(u,v))$四个点的线段树上一起二分就好了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
const int N=3e5+10;
ull mix(ull o){
    o+=0x9e3779b97f4a7c15;
    o=(o^(o>>30))*0xbf58476d1ce4e5b9;
    o=(o^(o>>27))*0x94d049bb133111eb;
    return o^(o>>31);
}
int n,q,a[N];
ull b[N];
vector<int> G[N];
int rt[N],ls[N*100],rs[N*100],sz;
ull xr[N*100];
inline void upd(int &cur,int pre,int l,int r,int pos,ull x){
    cur=++sz;
    ls[cur]=ls[pre];rs[cur]=rs[pre];
    if(l==r){xr[cur]=xr[pre]^x;return;}
    int mid=(l+r)>>1;
    if(pos<=mid) upd(ls[cur],ls[pre],l,mid,pos,x);
    else upd(rs[cur],rs[pre],mid+1,r,pos,x);
    xr[cur]=xr[ls[cur]]^xr[rs[cur]];
}
inline int get(int x,int y,int z,int w,int L,int R,int l,int r){
    if(L==R){if(xr[x]^xr[y]^xr[z]^xr[w]) return L;else return -1;}int mid=(L+R)>>1;
    if(l<=L&&r>=R){
        ull le=xr[ls[x]]^xr[ls[y]]^xr[ls[z]]^xr[ls[w]];
        ull ri=xr[rs[x]]^xr[rs[y]]^xr[rs[z]]^xr[rs[w]];
        if(le) return get(ls[x],ls[y],ls[z],ls[w],L,mid,l,r);
        else if(ri) return get(rs[x],rs[y],rs[z],rs[w],mid+1,R,l,r);
        else return -1;
    }
    int v1=-1,v2=-1;
    if(l<=mid) v1=get(ls[x],ls[y],ls[z],ls[w],L,mid,l,r);
    if(v1!=-1) return v1;
    if(r>mid) v2=get(rs[x],rs[y],rs[z],rs[w],mid+1,R,l,r);
    if(v2!=-1) return v2;
    return -1;
}
int size[N],son[N],fa[N],dep[N];
inline void dfs1(int x,int f){
    size[x]=1;son[x]=0;fa[x]=f;
    upd(rt[x],rt[f],1,n,a[x],b[x]);
    for(auto v:G[x]){
	if(v==f) continue;
	dep[v]=dep[x]+1;dfs1(v,x);size[x]+=size[v];
	if(size[v]>size[son[x]]) son[x]=v;
    }
}
int top[N],dfn[N],ed[N],pre[N],ind;
inline void dfs2(int x,int tp){
    top[x]=tp;dfn[x]=++ind;pre[ind]=x;
    if(son[x]){
	dfs2(son[x],tp);
        for(auto v:G[x]){
	    if(v==fa[x]||v==son[x]) continue;
	    dfs2(v,v);
	}
    }
    ed[x]=ind;
}
inline int LCA(int x,int y){
    for(;top[x]^top[y];x=fa[top[x]])
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
    return dep[x] < dep[y] ? x:y;
}
int main(){
    n=read();q=read();
    rep(i,1,n) a[i]=read();
    rep(i,1,n) b[i]=mix(a[i]);
    rep(i,1,n-1){
        int u=read(),v=read();
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs1(1,0);
    dfs2(1,1);
    while(q--){
        int u=read(),v=read(),l=read(),r=read();
        int t=LCA(u,v);
        printf("%d\n",get(rt[u],rt[v],rt[t],rt[fa[t]],1,n,l,r));
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.
Contents

CF1481Div2

dp选做1 By Oscar

Loading comments from Disqus ...