运输规划 题解

· · 题解

这里是官方题解。

sub1

不难发现这是一个二分图匹配模型，我们用卡车去匹配机场，由于要最小化字典序，所以考虑建出二分图，在字典序上按位贪心，每次考虑每个机场被哪个卡车匹配，匹配完后再跑一遍二分图匹配判断是否存在解。

sub2

一个卡车可以匹配的机场是一段前缀，不妨把机场看成左括号，卡车看成右括号，问题变成每次对于一个左括号找到编号最小的右括号，使得删去这两个括号后剩下的括号仍然可以匹配，考虑存在匹配的条件是任意一个前缀中左括号数量大于等于右括号数量，于是发现可以匹配的右括号具有单调性，线段树维护即可。

sub3

因为保证了 h_i 互不相同，所以可以建出唯一可能的笛卡尔树，建出笛卡尔树后，一个点所能到达的点成为了其在笛卡尔树上子树内所有点。

由于这是依然一个二分图是否存在完美匹配的问题，考虑霍尔定理。下文将卡车视作左部点，机场视作右部点。

假若你选出了一个左部点集合 S，我们令其中所有满足其祖先中（不包括自己）不存在左部点的左部点集合为 S'，显然对于所有 u \in S' 而言，我们假若将 u 所有子树中的左部点加入集合 S 得到新的集合 S''，那么我们发现 S'' 满足其邻域并大小等于 S 的邻域并大小，所以假若 S'' 的大小小于等于其邻域并大小，那么 S 的大小也一定小于等于其邻域并大小，那么我们只保留 S'' 的限制，然后考虑对于任意 u \in S' 而言，S'' 满足其大小小于等于其邻域并等价于所有 u 的子树中左部点集合 sub_u 的大小小于等于其邻域并，又因为我们可以只选择某个点来使得任意点 1 \leq u \leq n 在集合 S' 中，所以实际上存在完美匹配当且仅当任意点子树中的右部点数量大于等于子树中的左部点数量。

考虑令 val_u 等于一个点子树中的左部点数量减去子树中的右部点数量。显然一个存在完美匹配的局面等价于所有点的 val \leq 0。对于一个右部点 u，我们选择其祖先左部点 v 与其匹配，那么匹配完仍然存在一组完美匹配当且仅当 u \to v 路径上所有点（不包括 v）的 val \leq -1，因为匹配后这些点的 val 会加 1，因此操作之前不能等于 0。

而这是具有单调性的，我们找到 u 到根的链上最深的一个满足 val_x = 0 的点 x，那么我们可以选择的 v 实际上就是 u \to x 的链。因此暴力跳父亲找到满足条件的点中编号最小的即可。

sub4

考虑树链剖分维护链上深度最深的 val 最大点与链上编号最小点即可。

#include<bits/stdc++.h>
#define min(x,y) (x<y?x:y)
using namespace std;
const int maxn = 2e5+114;
int ls[maxn],rs[maxn],a[maxn];
int st[maxn],tp;
int dfn[maxn],node[maxn],dfc;
int rk[maxn];
const int inf = 1e9+114;
struct Mininfo{
    int Minrk;
    //最小 rk 节点的 rk
    Mininfo(){
        Minrk=inf;
    }
    Mininfo operator+(const Mininfo &x)const{
        Mininfo res=Mininfo();
        res.Minrk=min(Minrk,x.Minrk);
        return res;
    }
}tr[maxn<<2];
struct Maxinfo{
    int Maxval;
    int Maxdfn;
    //最大值
    //最大值的最大 dfn
    Maxinfo(){
        Maxval=Maxdfn=-inf;
    }
    Maxinfo operator+(const Maxinfo &x)const{
        Maxinfo res=Maxinfo();
        res.Maxval=Maxval;
        res.Maxdfn=Maxdfn;
        if(Maxval>x.Maxval) return res;
        else if(Maxval<x.Maxval){
            return x;
        }
        else{
            if(Maxdfn>x.Maxdfn) return res;
            else{
                return x;
            }
        }
    }
}Tr[maxn<<2];
int tag[maxn<<2];//下传加 1 标记
int father[maxn],son[maxn],sz[maxn],top[maxn],dep[maxn];
int val[maxn];
int S[maxn];
int n,m;
void dfs1(int u,int fa){
    if(u==0) return ;
    dep[u]=dep[fa]+1;
    father[u]=fa;
    sz[u]=1;
    dfs1(ls[u],u);
    dfs1(rs[u],u);
    val[u]+=val[ls[u]];
    val[u]+=val[rs[u]];
    sz[u]+=(sz[ls[u]]+sz[rs[u]]);
    if(sz[ls[u]]>sz[rs[u]]) son[u]=ls[u];
    else son[u]=rs[u];
}
void dfs2(int u,int t){
    if(u==0) return ;
    dfn[u]=++dfc;
    node[dfc]=u;
    top[u]=t;
    if(son[u]!=0) dfs2(son[u],t);
    if(son[u]!=ls[u]) dfs2(ls[u],ls[u]);
    else dfs2(rs[u],rs[u]);
}
void pushupMin(int cur){
    tr[cur]=tr[cur<<1]+tr[cur<<1|1];
}
void pushupMax(int cur){
    Tr[cur]=Tr[cur<<1]+Tr[cur<<1|1];
}
void pushdown(int cur){
    Tr[cur<<1].Maxval+=tag[cur];
    tag[cur<<1]+=tag[cur];
    Tr[cur<<1|1].Maxval+=tag[cur];
    tag[cur<<1|1]+=tag[cur];
    tag[cur]=0;
}
void del(int cur,int lt,int rt,int p){
    if(lt==rt){
        Tr[cur].Maxval--;
        tr[cur].Minrk=inf;
        return ;
    }
    int mid=(lt+rt)>>1;
    pushdown(cur);
    if(p<=mid) del(cur<<1,lt,mid,p);
    else del(cur<<1|1,mid+1,rt,p);
    pushupMax(cur);
    pushupMin(cur);
}//dfn[] = p 的数删掉
Mininfo askMin(int cur,int lt,int rt,int l,int r){
    if(l>r) return Mininfo();
    if(l<=lt&&rt<=r){
        return tr[cur];
    }
    int mid=(lt+rt)>>1;
    Mininfo res=Mininfo();
    if(l<=mid) res=res+askMin(cur<<1,lt,mid,l,r);
    if(r>mid) res=res+askMin(cur<<1|1,mid+1,rt,l,r);
    return res;
}
Mininfo askMin_list(int u,int v){
    Mininfo res=Mininfo();
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        res=res+askMin(1,1,n,dfn[top[u]],dfn[u]);
        u=father[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    res=res+askMin(1,1,n,dfn[v],dfn[u]);
    return res;
}
void add(int cur,int lt,int rt,int l,int r){
    if(l>r) return ;
    if(l<=lt&&rt<=r){
        Tr[cur].Maxval++;
        tag[cur]++;
        return ;
    }
    int mid=(lt+rt)>>1;
    pushdown(cur);
    if(l<=mid) add(cur<<1,lt,mid,l,r);
    if(r>mid) add(cur<<1|1,mid+1,rt,l,r);
    pushupMax(cur);
}
void add_list(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        add(1,1,n,dfn[top[u]],dfn[u]);
        u=father[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    add(1,1,n,dfn[v],dfn[u]);
}
Maxinfo askMax(int cur,int lt,int rt,int l,int r){
    if(l>r) return Maxinfo();
    if(l<=lt&&rt<=r){
        return Tr[cur];
    }
    int mid=(lt+rt)>>1;
    Maxinfo res=Maxinfo();
    pushdown(cur);
    if(l<=mid) res=res+askMax(cur<<1,lt,mid,l,r);
    if(r>mid) res=res+askMax(cur<<1|1,mid+1,rt,l,r);
    return res;
}
Maxinfo askMax_list(int u,int v){
    Maxinfo res=Maxinfo();
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        res=res+askMax(1,1,n,dfn[top[u]],dfn[u]);
        u=father[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    res=res+askMax(1,1,n,dfn[v],dfn[u]);
    return res;
}
void build(int cur,int lt,int rt){
    if(lt==rt){
        tr[cur]=Mininfo();
        tr[cur].Minrk=(S[node[lt]]==true?rk[node[lt]]:inf);
        Tr[cur]=Maxinfo();
        Tr[cur].Maxdfn=(S[node[lt]]==true?lt:-inf);
        Tr[cur].Maxval=val[node[lt]];
        return ;
    }
    int mid=(lt+rt)>>1;
    build(cur<<1,lt,mid);
    build(cur<<1|1,mid+1,rt);
    pushupMax(cur);
    pushupMin(cur);
}
vector<int> ans;//答案序列
vector<int> s,T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        int k=tp;
        while(k>0&&a[st[k]]>a[i]) k--;
        if(k) rs[st[k]]=i;
        if(k<tp) ls[i]=st[k+1];
        st[++k]=i,tp=k;
    }
    for(int i=1;i<=m;i++){
        int u;
        cin>>u;
        s.push_back(u);
        rk[u]=s.size();
        S[u]=1;
        val[u]++;
    }
    for(int i=1;i<=m;i++){
        int u;
        cin>>u;
        T.push_back(u);
        val[u]--;
    }
    dfs1(st[1],0);
    dfs2(st[1],st[1]);
    build(1,1,n);
    for(int x:T){
        Maxinfo now=askMax_list(x,st[1]);
        if(now.Maxval!=0) now.Maxdfn=1;
        int u=node[now.Maxdfn];
        Mininfo res=askMin_list(x,u);
        int to=res.Minrk;
        ans.push_back(to);
        add_list(x,s[to-1]);
        del(1,1,n,dfn[s[to-1]]);
    }
    for(int x:ans) cout<<x<<' ';
    return 0;
}