题解：P13540 [IOI 2025] Obstacles for a Llama

· · 题解

下面是 vp 时的做法，由于一些原因可能做复杂了。

首先看上去非常的奇怪，我们关注一下限制最松的一部分，也就是 h 最小的若干列 p_1,p_2,\dots,p_k。

考虑对这些列做分治，也就是将区间 [l,r] 分为 [l,p_1),(p_1,p_2),\dots,(p_k,r]，然后去递归这些区间内部的连边，然后再考虑区间之间的连边。

考虑区间之间的连边，注意到区间 (p_i,p_{i+1}) 想连边出去必须先抵达抵达列 p_i+1 或者列 p_{i+1}-1，不妨记能抵达这些列的连通块集合为 L,R。

注意到区间 (p_i,p_{i+1}) 中的限制严格强于 p_i,p_{i+1}，所以如果从区间 (p_i,p_{i+1}) 中走出来可以走到第 p_i,p_{i+1} 列的第 j 行，那么必定可以从 (p_i,0),(p_{i+1},0) 直接走到 (p_i,j),(p_{i+1},j)。

所以我们会把集合 L,R 中的连通块分别与 (p_i,0),(p_{i+1},0) 代表的连通块合并。

再考虑 p_i,p_k 之间的连边，预处理出 (p_i,0) 可以抵达的前缀中最大行 q，那么 (p_i,0),(p_k,0) 如果满足 \max_{j=i}^k h_j < t_p 就将其合并。

当递归完 [l,r] 返回时，再以 [l,p_1),(p_k,r] 最左边和最右边的连通块集合作为 L,R 返回。

写一发，交上去发现过不了。

你发现漏掉了 p_1,p_k 分别抵达 l,r 的情形，更进一步地，如果其可以抵达区间端点并且区间端点不是 0,m-1，那么其一定会与 [l,p_1),(p_k,r] 中可以抵达区间端点的连通块在某个时刻合并，所以不妨直接在返回 L,R 时直接将其中所有连通块合并一同返回。

到这里可以过掉最后一个子任务之前的所有子任务。

考虑正解，不妨把合并过程建树，然后把每个点在合并过程中强制拐弯的位置刻画出来。

所谓强制拐弯，就是如果 (p_i,p_{i+1}) 返回了两个不同的连通块 L,R，那么当把 L 合并到 p_i 上时，你发现 L 内的点出来后不管向左或者向右都要经过 p_i，这就要给 L 设置一个虚拟父亲并打上 p_i 的强制拐弯标记，对于 R 同理。

在处理递归完返回的 L,R 时也需要类似地打标记。

查询就在由合并建立的树上在链查询标记 \max,\min 即可，容易倍增做到 O(q \log n)。

细节比较多，可以看代码。

事实上，因为我的做法建出的是广义笛卡尔树所以有较多的分类讨论，但注意到相同值并不需要特殊处理，所以可以直接建一般笛卡尔树（也就是每次随意取出一个最小值位置去分治）减少很多细节。

下面贴出一般笛卡尔树写法的代码：

#include<bits/stdc++.h>
#include "obstacles.h"
#define fir first
#define sec second
using namespace std;
const int maxn = 6e5+114;
int t[maxn],h[maxn],n,m;
int fa[maxn];
int mx[maxn<<2];
pair<int,int> mi[maxn<<2];
void build(int cur,int lt,int rt){
    if(lt==rt){
        mi[cur]=make_pair(h[lt],lt);
        mx[cur]=h[lt];
        return ;
    }
    int mid=(lt+rt)>>1;
    build(cur<<1,lt,mid),build(cur<<1|1,mid+1,rt);
    mi[cur]=min(mi[cur<<1],mi[cur<<1|1]);
    mx[cur]=max(mx[cur<<1],mx[cur<<1|1]);
}
pair<int,int> askmi(int cur,int lt,int rt,int l,int r){
    if(rt<l||r<lt) return make_pair(1e9+114,-1);
    if(l<=lt&&rt<=r) return mi[cur];
    int mid=(lt+rt)>>1;
    return min(askmi(cur<<1,lt,mid,l,r),askmi(cur<<1|1,mid+1,rt,l,r));
}
int askmx(int cur,int lt,int rt,int l,int r){
    if(rt<l|r<lt) return -1;
    if(l<=lt&&rt<=r) return mx[cur];
    int mid=(lt+rt)>>1;
    return max(askmx(cur<<1,lt,mid,l,r),askmx(cur<<1|1,mid+1,rt,l,r));
}
int find(int u){
    return fa[u]=(fa[u]==u?u:find(fa[u]));
}
int premi[maxn],premx[maxn];
vector<int> E[maxn<<1];
int val[maxn<<1];
int jump[maxn][20],Mx[maxn][20],Mi[maxn][20];
int dep[maxn],lg[maxn];
int tot;
void dfs(int u,int lst){
    if(lst==-1) dep[u]=1;
    else dep[u]=dep[lst]+1;
    jump[u][0]=lst;
    Mx[u][0]=(val[u]==-1?-1e9:val[u]);
    Mi[u][0]=(val[u]==-1?1e9:val[u]);
    for(int i=1;i<20;i++){
        if(jump[u][i-1]==-1){
            jump[u][i]=-1;
            Mx[u][i]=Mx[u][i-1];
            Mi[u][i-1]=Mi[u][i-1];
        }
        else{
            jump[u][i]=jump[jump[u][i-1]][i-1];
            Mx[u][i]=max(Mx[u][i-1],Mx[jump[u][i-1]][i-1]);
            Mi[u][i]=min(Mi[u][i-1],Mi[jump[u][i-1]][i-1]);
        }
    }
    for(int nxt:E[u]){
        dfs(nxt,u);
    }
}
pair<int,int> solve(int l,int r){
    //返回可以靠到最左边/右边的连通块
    int pos=askmi(1,0,m-1,l,r).sec;
    int v=h[pos];
    if(v>=t[0]) return make_pair(-1,-1);
    pair<int,int> res=make_pair(-1,-1);
    if(pos!=l){
        pair<int,int> son=solve(l,pos-1);
        bool flag=false;
        if(son.fir!=-1&&son.sec!=-1&&find(son.fir)==find(son.sec)) flag=true;
        if(son.fir!=-1) res.fir=find(son.fir);
        if(son.sec!=-1){
            if(find(son.sec)!=find(pos)){
                if(flag==false){
                    tot++;
                    E[tot].push_back(find(son.sec));
                    E[find(pos)].push_back(tot);
                    fa[find(son.sec)]=fa[tot]=find(pos);  
                    val[tot]=pos;
                }else{
                    tot++;
                    E[tot].push_back(find(son.sec));
                    E[tot].push_back(find(pos));
                    fa[find(son.sec)]=fa[find(pos)]=fa[tot]=tot;
                    val[tot]=-1;
                }
            }
        }
    }else res.fir=find(pos);
    if(pos!=r){
        pair<int,int> son=solve(pos+1,r);
        bool flag=false;
        if(son.fir!=-1&&son.sec!=-1&&find(son.fir)==find(son.sec)) flag=true;
        if(son.fir!=-1){
            if(find(son.fir)!=find(pos)){
                if(flag==false){
                    tot++;
                    E[tot].push_back(find(son.fir));
                    E[find(pos)].push_back(tot);
                    fa[find(son.fir)]=fa[tot]=find(pos);   
                    val[tot]=pos;                 
                }else{
                    tot++;
                    E[tot].push_back(find(son.fir));
                    E[tot].push_back(find(pos));
                    fa[find(son.fir)]=fa[find(pos)]=fa[tot]=tot;
                    val[tot]=-1;
                }
            }
        }
        if(son.sec!=-1) res.sec=find(son.sec);
    }else res.sec=find(pos);
    int L=0,R=n;
    while(L+1<R){
        int mid=(L+R)>>1;
        if(premi[mid]>v) L=mid;
        else R=mid;
    }
    int edge=premx[L];
    if(askmx(1,0,m-1,l,pos)<edge){
        if(res.fir==-1) res.fir=find(pos);
        else if(l!=0){
            if(find(res.fir)!=find(pos)){
                tot++;
                E[tot].push_back(find(res.fir));
                val[tot]=l-1;
                tot++;
                E[tot].push_back(tot-1);
                E[tot].push_back(find(pos));
                fa[find(res.fir)]=fa[tot-1]=fa[find(pos)]=fa[tot]=tot;
                val[tot]=-1;
            }
        }
    }
    if(askmx(1,0,m-1,pos,r)<edge){
        if(res.sec==-1) res.sec=find(pos);
        else if(r!=m-1){
            if(find(res.sec)!=find(pos)){
                tot++;
                E[tot].push_back(find(res.sec));
                val[tot]=r+1;
                tot++;
                E[tot].push_back(tot-1);
                E[tot].push_back(find(pos));
                fa[find(res.sec)]=fa[tot-1]=fa[find(pos)]=fa[tot]=tot;
                val[tot]=-1;
            }
        }
    }
    return res;
}
void initialize(std::vector<int> T, std::vector<int> H){
    n=T.size(),m=H.size();
    for(int i=0;i<n;i++) t[i]=T[i];
    for(int i=0;i<m;i++) h[i]=H[i];
    for(int i=0;i<m;i++) fa[i]=i;
    build(1,0,m-1);
    for(int i=0;i<m;i++) val[i]=i;
    tot=m-1;
    premi[0]=premx[0]=t[0];
    for(int i=1;i<n;i++){
        premi[i]=min(premi[i-1],t[i]);
        premx[i]=max(premx[i-1],t[i]);
    }
    lg[1]=0;
    for(int i=2;i<maxn;i++) lg[i]=lg[i>>1]+1;
    solve(0,m-1);
    for(int i=0;i<=tot;i++){
        if(find(i)==i) dfs(i,-1);
    }    
}
bool can_reach(int L, int R, int S, int D){
    if(find(S)!=find(D)) return false;
    int mx=-1e9,mi=1e9;
    if(dep[S]<dep[D]) swap(S,D);
    while(dep[S]>dep[D]){
        mx=max(mx,Mx[S][lg[dep[S]-dep[D]]]);
        mi=min(mi,Mi[S][lg[dep[S]-dep[D]]]);
        S=jump[S][lg[dep[S]-dep[D]]];
    }
    if(S!=D){
        for(int i=19;i>=0;i--){
            if(jump[S][i]!=jump[D][i]){
                mx=max(mx,max(Mx[S][i],Mx[D][i]));
                mi=min(mi,min(Mi[S][i],Mi[D][i]));
                S=jump[S][i],D=jump[D][i];
            }
        }
        mx=max(mx,max(Mx[S][0],Mx[D][0]));
        mi=min(mi,min(Mi[S][0],Mi[D][0]));
        S=jump[S][0],D=jump[D][0];
    }
    mx=max(mx,Mx[S][0]);
    mi=min(mi,Mi[S][0]);
    if(mx>R||mi<L) return false;
    return true;
}