P9726 [EC Final 2022] Magic 可持久化线段树优化建图

六楼溜刘 · 2023-11-28 08:16:47 · 题解

题意

这道题翻译是我提交的，自己去看翻译。

• 你有一个序列 a_0,a_1,a_2\dots a_{2n}，初始全为 0。
• 给定 n 个区间赋值操作，第 i 个操作 (l_i,r_i)(1\le l_i,r_i\le 2n) 表示把区间 [l_i,r_i) 全部赋值为 i，保证所有 l_i,r_i 互不相同。
• 你可以指定一个执行操作的顺序，最大化 \sum_{i=0}^{2n-1}[a_i\ne a_{i+1}]，输出这个最大值。

题解

首先可以分三种情况转化为二分图最大独立集问题，具体转化可以参考 lzq 大佬的这篇题解，这里主要讲他提到但是没有具体说明的可持久化线段树优化建图。

他题解里说有这种方法于是我去网上找题解结果没找到，然后我就自己琢磨着写了一个。

首先考虑问题的转化，对于一对 (l_x,r_x)(l_y,r_y)（假设 l_x<l_y），r_x,l_y 之间何时会连边。考虑把 l 作为横坐标，r 作为纵坐标，建出坐标系。原本的限制是 l_x<l_y<r_x<r_y，即当 x 的纵坐标 r_x\in (l_y,r_y)，横坐标 l_x<l_y 时，r_x 和 l_y 之间会连一条边。

大概是这样的一些向左无限延长的矩形，然后一个矩形 (l_y,r_y) 的 l_y 需要和它包含的所有点对应的 r_x 连一条边。

为什么要这样转化呢？因为通过线段树优化建图的经验，我们发现向一段连续的区间连边是可维护的，而如果转化为类似“一个点要向包含它的所有矩形连边”就不好维护了。

那么考虑一个类似于扫描线的算法，即维护一条从左到右的扫描线，每次向区间连边，然后把点 (l_i,r_i) 挂在区间上的 r_i 位置。但是线段树优化建图要求所有点已经被挂在序列上，即必须离线下来，考虑用其它数据结构转化成在线加点。

这时候看了标题聪明的同学就能想到用可持久化线段树。

具体来说，每次加入一个点 (l_i,r_i) 的时候，在 i-1 版本的基础上新建一个版本，除去新增 r_i 对应的一条树链以外，其余配置完全继承 i-1。这样就能实现加点了。

注意新增的这条树链要记得和从前一个版本中继承的儿子连边。

总结一下，遇到序列上点会增加/减少，但是要向区间连边时可以考虑主席树优化建图。（删点怎么维护应该很简单吧？）

然后考虑边权问题，即考虑新加的这些边容量应该取多少。我之前纠结了半天数据结构优化建图怎么赋容量才能等价于向区间所有点连一条容量为 1 的边。但其实不用这么麻烦，因为是二分图匹配问题，所以中间的边容量是可以取正无穷的！然后就做完了，在新建出来的图上跑一遍 dinic 即可，空间复杂度 O(n\log n)，时间复杂度大概是 O(n^3\log n)，但这毕竟是 dinic 的复杂度，一般情况下不会被卡的。

code

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=5005;
int n,cntn;
struct Node{
    int l,r;
}s[N];
struct flow{//dinic 板子
    struct edge{
        int v,rst,nxt;
    }e[N*80];//注意边数开大一点
    int head[N*20],cur[N*20],cnte=1,dpt[N*20],s,t;
    void adde(int u,int v,int w){
        e[++cnte]=edge{v,w,head[u]};head[u]=cnte;
        e[++cnte]=edge{u,0,head[v]};head[v]=cnte;
    }
    bool bfs(){
        forup(i,1,cntn){
            cur[i]=head[i];
            dpt[i]=-1;
        }
        queue<int> q;
        q.push(s);dpt[s]=0;
        while(q.size()){
            int u=q.front();q.pop();
            for(int i=head[u];i;i=e[i].nxt){
                int v=e[i].v;
                if(dpt[v]!=-1||!e[i].rst) continue;
                dpt[v]=dpt[u]+1;
                q.push(v);
            }
        }
        return dpt[t]!=-1;
    }
    int dfs(int x,int flow){
        if(x==t||!flow) return flow;
        int res=0;
        for(int i=cur[x];i;i=e[i].nxt){
            cur[x]=i;int v=e[i].v;
            if(dpt[v]!=dpt[x]+1||!e[i].rst) continue;
            int gt=dfs(v,min((int)e[i].rst,flow-res));
            if(gt){
                res+=gt;
                e[i].rst-=gt;
                e[i^1].rst+=gt;
                if(res==flow) break;
            }
        }
        return res;
    }
    int dinic(){
        int ans=0;
        while(bfs()){
            ans+=dfs(s,n);//这里正无穷取的 n，因为流量不会超过 n。
        }
        return ans;
    }
}mf;
struct SegTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,ls[id]
    #define rson mid+1,r,rs[id]
    int num[N*15],cntt,ls[N*15],rs[N*15];
    void Update(int P,int X,int l,int r,int id,int o){//新加入一个点
        if(l==r){
            num[id]=X;
            return;
        }
        num[id]=++cntn;
        if(P<=mid){
            ls[id]=++cntt;rs[id]=rs[o];
            Update(P,X,lson,ls[o]);
            mf.adde(num[id],num[ls[id]],n);
            if(rs[id]) mf.adde(num[id],num[rs[id]],n);
        }else{
            rs[id]=++cntt;ls[id]=ls[o];
            Update(P,X,rson,rs[o]);
            mf.adde(num[id],num[rs[id]],n);
            if(ls[id]) mf.adde(num[id],num[ls[id]],n);
        }
    }
    void Link(int L,int R,int X,int l,int r,int id){//向区间连边
        if(L<=l&&r<=R){
            mf.adde(X,num[id],n);
            return;
        }
        if(L<=mid&&ls[id]) Link(L,R,X,lson);
        if(mid< R&&rs[id]) Link(L,R,X,rson);
    }
}mt;
signed main(){
    n=read();
    forup(i,1,n){
        s[i].l=read();s[i].r=read();
    }
    sort(s+1,s+n+1,[&](Node a,Node b){
        return a.l<b.l;
    });
    mf.s=n*2+1;mf.t=n*2+2;
    mt.cntt=n;cntn=n*2+2;
    forup(i,1,n){
        mf.adde(mf.s,i,1);mf.adde(i+n,mf.t,1);
        mt.Link(s[i].l,s[i].r,i,1,n*2,i-1);
        mt.Update(s[i].r,i+n,1,n*2,i,i-1);
            //这里点的序号是随便取的，左部点是 [1,n]，右部点是 [n+1,2n]
    }
    printf("%d\n",n*2-mf.dinic());//注意最大独立集是最小点覆盖的补集
}