题解：P12180 DerrickLo's City (UBC002C)

· · 题解

分析

直接算吧。先把 \operatorname{LCA}(l,l+1,\dots,r) 求出来，记为 x。然后分类讨论：

所以现在问题变成了一个判定区间内是否存在一对点 (i,j)，使得其中一个是另一个的祖先。这个是个典的东西。我们对于每个点 u 记录 pre_u 表示 u 子树中最大的满足 v < u 的 v 值，nxt_u 表示 u 子树中最小的满足 v>u 的 v 值。那么当 [l,r] 中存在一个点 i，满足 pre_i \ge l \lor nxt_i \le r，就一定存在至少一对点了。预处理这个可以跑一遍 DFS。

求区间 \operatorname{LCA} 是典 trick，区间中相邻两个 \operatorname{LCA} 深度最小的就是区间的 \operatorname{LCA}。

但是这么做会有一点小问题。就是如果我们一共有 2 个点，且它们相邻，我们并不会判定它们不行。为什么呢，因为我们只看了 y \ne x。而 y \ne x 时我们决策的 p 是在 y 点上的。所以如果 y 上面有点就错了。这个特殊处理即可。那为什么点数 >2 时不会错呢，因为我们一定有 y 子树内某个点 z 属于区间 [l,r]，已经判掉了。

这样做的时间复杂度为 O(n\log n+q)，标程在写什么。

代码

il void dfs(int u,int fa){
    dep[u]=dep[fa]+1,
    f[u][0]=fa;
    for(re int i=1;i<20;++i) f[u][i]=f[f[u][i-1]][i-1];
    auto it=st.lower_bound(u);
    if(it!=st.begin()){
        --it;
        nxt[*it]=min(nxt[*it],u);
    }
    it=st.lower_bound(u);
    if(it!=st.end()){
        pre[*it]=max(pre[*it],u);
    }
    st.insert(u);
    for(auto v:e[u])
    if(v!=fa) dfs(v,u);
    st.erase(u);
    return ;
}
il int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(re int i=19;i>=0;--i) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    for(re int i=19;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0]; 
}
il int query_lca(int l,int r){
    if(l>r) return l;
    int k=__[r-l+1];
    if(dep[lc[l][k]]<=dep[lc[r-(1ll<<k)+1][k]]) return lc[l][k];
    return lc[r-(1ll<<k)+1][k];
}
il int query_min(int l,int r){
    if(l>r) return inf;
    int k=__[r-l+1];
    return min(Min[l][k],Min[r-(1ll<<k)+1][k]);
}
il int query_max(int l,int r){
    if(l>r) return -inf;
    int k=__[r-l+1];
    return max(Max[l][k],Max[r-(1ll<<k)+1][k]);
}

il void solve(){
    n=rd,q=rd;
    for(re int i=1;i< n;++i){
        int u=rd,v=rd;
        e[u].push_back(v),
        e[v].push_back(u); 
    }
    for(re int i=1;i<=n;++i) pre[i]=-inf,nxt[i]=inf;
    dfs(1,0);
    for(re int i=0;i< N;++i) __[i]=log2(i);
    for(re int i=1;i<=n;++i){
        if(i<n) lc[i][0]=lca(i,i+1);
        Min[i][0]=nxt[i],
        Max[i][0]=pre[i];
    }
    for(re int j=1;j<20;++j)
    for(re int i=1;i+(1ll<<j)-1<=n;++i){
        if(dep[lc[i][j-1]]<=dep[lc[i+(1ll<<(j-1))][j-1]]) lc[i][j]=lc[i][j-1];
        else lc[i][j]=lc[i+(1ll<<(j-1))][j-1];
        Min[i][j]=min(Min[i][j-1],Min[i+(1ll<<(j-1))][j-1]),
        Max[i][j]=max(Max[i][j-1],Max[i+(1ll<<(j-1))][j-1]);
    }
    while(q--){
        int l=rd,r=rd;
        if(l==r){
            puts("Yes");
            continue;
        }
        int x=query_lca(l,r-1);
        if(x<l||x>r){
            int mx=query_max(l,r);
            int mi=query_min(l,r);
            if(mx>=l||mi<=r) puts("No");
            else puts("Yes");
        }
        else{
            int Lca;
            if(x==l) Lca=query_lca(l+1,r-1);
            else if(x==r) Lca=query_lca(l,r-2);
            else Lca=lca(query_lca(l,x-2),query_lca(x+1,r-1));
            if(Lca==x){
                puts("No");
                continue;
            }
            if(dep[Lca]==dep[x]+1&&r-l+1==2){
                puts("No");
                continue;
            }
            int mi=min(query_min(l,x-1),query_min(x+1,r));
            int mx=max(query_max(l,x-1),query_max(x+1,r));
            if(mi<=r||mx>=l) puts("No");
            else puts("Yes");
        }
    }
    return ;
}