【UOJ#77】A+B Problem | Mrsrz's blog

可持久化线段树优化建图，最小割

题目大意：

有 $n$ 个点，第 $i$ 个点染成黑色得到 $b_i$ 的价值，染成白色得到 $w_i$ 的价值。

如果第 $i$ 个点是黑色，且存在 $1\leq j\lt i$ ，满足 $l_i\leq a_j\leq r_i$ 且 $j$ 是白色，则减少 $p_i$ 的价值。

求最大总价值。

题解：

考虑将问题变成一个最小割问题。

我们将源点连向 $i$ 的边看作染黑，$i$ 连向汇点的边看作染白。则割一条边相当于不染这种颜色。一个点只能有一种颜色，所以要求源汇不连通。要求减去的代价最小，则求最小割即可。

考虑限制关系。我们枚举 $j$，对满足 $j\lt i$ 且 $l_i\leq a_j\leq r_i$ 的点 $j$，由 $i$ 向 $j$ 连容量为 $p_i$ 的边。这样若 $i$ 选黑而 $j$ 选白，则源点通过 $i$ 和 $j$ 到汇点连通，因此要割掉这条边，花费代价为 $p_i$。

对建出来的图跑最大流，用 $b$ 和 $w$ 的总和减去最大流即可。

边数是 $O(n^2)$ 的，无法接受。

考虑优化建图。

我们用可持久化线段树对每个 $i$ 维护 $1\sim i$ 结点的连边的树形结构，然后对每个 $i$，在可持久化线段树上找到 $l_i,r_i$ 对应的区间连边即可。要对 $a$ 进行离散化，否则点数和边数将会乘 $\log a$ 而不是 $\log n$，导致效率低下。

这样点数和边数都是 $O(n\log n)$ 的，可以通过。

注意可持久化线段树优化建图的一些细节，新的点要向原来的点连边。

Code：

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=5005,M=220005;
typedef long long LL;
const LL inf=1e16;
int n,head[M],iter[M],cnt=1,T,nod,rt[N],d[M],ls[M],rs[M],n_sg,dep[M];
LL sum,fl;
struct edge{
    int to,nxt;LL cap;
}e[M*4];
inline void addedge(int u,int v,LL cap){
    e[++cnt]=(edge){v,head[u],cap},head[u]=cnt;
    e[++cnt]=(edge){u,head[v],0},head[v]=cnt;
}
void addnode(int&o,int pre,int l,int r,const int&pos,const int&id){
    o=++n_sg,ls[o]=ls[pre],rs[o]=rs[pre],d[o]=++nod;
    if(pre)addedge(d[o],d[pre],inf);
    if(l<r){
        const int mid=(l+r)/2;
        if(pos<=mid)addnode(ls[o],ls[pre],l,mid,pos,id);
        else addnode(rs[o],rs[pre],mid+1,r,pos,id);
        if(ls[o])addedge(d[o],d[ls[o]],inf);
        if(rs[o])addedge(d[o],d[rs[o]],inf);
    }else addedge(d[o],id,inf);
}
void link(int o,int l,int r,const int&L,const int&R,const int&id){
    if(!o)return;
    if(L<=l&&r<=R)addedge(id,d[o],inf);else{
        const int mid=(l+r)/2;
        if(L<=mid)link(ls[o],l,mid,L,R,id);
        if(mid<R)link(rs[o],mid+1,r,L,R,id);
    }
}
queue<int>q;
void bfs(){
    for(q.push(0);!q.empty();){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        if(e[i].cap&&!dep[e[i].to]){
            dep[e[i].to]=dep[u]+1;
            q.push(e[i].to);
        }
    }
}
LL dfs(int u,LL f){
    if(u==T||!f)return f;
    for(int&i=iter[u];i;i=e[i].nxt)if(e[i].cap&&dep[e[i].to]>dep[u]){
        LL d=dfs(e[i].to,min(f,e[i].cap));
        if(d){
            e[i].cap-=d,e[i^1].cap+=d;
            return d;
        }
    }
    return 0;
}
void flow(){
    for(;;){
        memset(dep,0,sizeof dep);
        dep[0]=1;
        bfs();
        if(!dep[T])break;
        memcpy(iter,head,sizeof iter);
        while(LL f=dfs(0,inf))fl+=f;
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    T=nod=n+1;
    static int A[N],B[N],W[N],L[N],R[N],P[N],db[N];
    for(int i=1;i<=n;++i)cin>>A[i]>>B[i]>>W[i]>>L[i]>>R[i]>>P[i],db[i]=A[i];
    sort(db+1,db+n+1);
    int M=unique(db+1,db+n+1)-db-1;
    for(int i=1;i<=n;++i){
        int a=A[i],b=B[i],w=W[i],l=L[i],r=R[i],p=P[i];
        a=lower_bound(db+1,db+M+1,a)-db;
        l=lower_bound(db+1,db+M+1,l)-db;
        r=upper_bound(db+1,db+M+1,r)-db-1;
        addnode(rt[i],rt[i-1],1,M,a,i);
        sum+=b+w;
        addedge(0,i,b),addedge(i,T,w);
        int x=++nod;
        addedge(i,x,p);
        link(rt[i-1],1,M,l,r,x);
    }
    flow();
    cout<<sum-fl<<'\n';
    return 0;
}