P9726 [EC Final 2022] Magic

· · 题解

“这不是简单题吗，为什么是黑啊？”——marblue

记位置 i 会对答案产生贡献当且仅当 a_{i-1}\neq a_i，问题可以转化成在 2n 个点中选最多的贡献给答案，现在考虑限制。对于两个区间 [l_1,r_1),[l_2,r_2)，我们分情况讨论一下：

发现题目保证 l_i,r_i 互不相等，故这是一个二分图，跑 bitset 优化 dinic/匈牙利即可，复杂度 \mathcal{O}(\dfrac{n^3}{w})/\mathcal{O}(\dfrac{n^2\sqrt{n}}{w})。似乎还可以用可持久化线段树优化建图的 dinic，好像是 \mathcal{O}(n^2\log n)，但我不太会（

是 luogu 上的倒数第二劣解，不知道为什么 dinic 这么慢啊，可能复杂度假了？

证明一下为什么找到独立集后一定有对应解。无解当且仅当对于区间执行顺序的先后限制构成环。考虑找到这个环上随便一个区间 [l_1,r_1)，假设它取的是右端点 r_1 产生贡献，找到它下一个区间 [l_2,r_2)，l_1<l_2,r_1<r_2，此时只能是 r_2 产生贡献。于是递归下去，因为 r_i 互不相同，所以环上的区间的 r 单调递增，故不会形成环。

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int n,S,T,dep[10005];bitset<10005>g[10005];
int bfs(){
    for(int i=1;i<=T;i++)dep[i]=0;
    dep[S]=1;queue<int>q;q.push(S);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int v=g[u]._Find_first();v<=T;v=max(v+1,(int)g[u]._Find_next(v))){
            if(g[u][v]==0)continue;
            if(!dep[v])dep[v]=dep[u]+1,q.push(v);
        }
    }
    return dep[T];
}
int dinic(int u,int flow){
    if(u==T)return flow;
    int rest=0;
    for(int v=g[u]._Find_first();v<=T&&flow;v=max(v+1,(int)g[u]._Find_next(v))){
        if(g[u][v]==0)break;
        if(dep[v]!=dep[u]+1)continue;
        int k=dinic(v,min(flow,1));if(!k)dep[v]=0;
        rest+=k,flow-=k;if(k)g[u][v]=0,g[v][u]=1;
    }
    return rest;
}
int l[5005],r[5005],pos[10005];
signed main(){
    n=read(),S=2*n+1,T=2*n+2;
    for(int i=1;i<=n;i++){
        l[i]=read(),r[i]=read();
        pos[l[i]]=0,pos[r[i]]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(l[i]<l[j]&&l[j]<r[i]&&r[i]<r[j]){
                g[l[j]][r[i]]=1;
            }
        }
    }
    for(int i=1;i<=2*n;i++)if(pos[i]==0)g[S][i]=1;
    for(int i=1;i<=2*n;i++)if(pos[i]==1)g[i][T]=1;
    int ans=2*n;
    while(bfs())ans-=dinic(S,inf);
    printf("%d\n",ans); 
    return 0;
}