[ 网络流 主席树 ] BZOJ3218

将答案转化为

∑(wi+bi)−∑whitebi−∑blackwi−∑strangepi

然后就是和 bzoj3681一样的套路。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 1e9
#define N 5010
#define M 200000
inline char nc(){
    static char buf[],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
inline void Read(int& x){
    char c=nc();
    for(;c<'0'||c>'9';c=nc());
    for(x=;c>='0'&&c<='9';x=(x<<)+(x<<)+c-,c=nc());
}
int cl[M],cr[M];
int i,j,k,n,m,cnt,t;
int Rt[N];
int a[N],b[N],w[N],L[N],R[N],p[N];
int c[N*],l,Ans;
namespace gjghfd{
    struct Edge{
        int t,nx,c;
    }e[];
    int h[M],d[M],cur[M],num=;
    bool b[M];
    int q[M];
    inline void Add(int x,int y,int w){
        e[++num].t=y;e[num].c=w;e[num].nx=h[x];h[x]=num;
        e[++num].t=x;e[num].c=;e[num].nx=h[y];h[y]=num;
    }
    inline bool Bfs(){
        memset(b,,sizeof(b));
        b[]=;int l=,r=;q[]=;
        while(++l<=r){
            int x=q[l];
            for(int i=h[x];i;i=e[i].nx)
            if(e[i].c&&!b[e[i].t])
            b[e[i].t]=,d[e[i].t]=d[x]+,q[++r]=e[i].t;
        }
        return b[t];
    }
    inline int Dfs(int x,int y){
        if(!y||x==t)return y;
        int Ans=;
        for(int& i=cur[x];i;i=e[i].nx){
            int v=e[i].t,f;
            if(d[v]==d[x]+&&(f=Dfs(v,min(y,e[i].c)))){
                Ans+=f;y-=f;e[i].c-=f;e[i^].c+=f;
                if(!y)break;
            }
        }
        if(y)d[x]=-;
        return Ans;
    }
    inline int Dinic(){
        int Ans=;
        while(Bfs()){
            for(int i=;i<=t;i++)cur[i]=h[i];
            Ans+=Dfs(,INF);
        }
        return Ans;
    }
}
inline void Update(int& x,int y,int f,int l,int r,int z){
    x=++cnt;
    if(f)gjghfd::Add(x,f,INF);
    if(y)gjghfd::Add(y,x,INF);
    if(l==r){
        gjghfd::Add(z<<,x,INF);
        return;
    }
    int Mid=l+r>>;
    if(a[z]<=Mid)cr[x]=cr[y],Update(cl[x],cl[y],x,l,Mid,z);else
    cl[x]=cl[y],Update(cr[x],cr[y],x,Mid+,r,z);
}
inline void Query(int x,int l,int r,int L,int R,int y){
    if(!x||l>R||r<L)return;
    if(l>=L&&r<=R){
        gjghfd::Add(x,y,INF);
        return;
    }
    int Mid=l+r>>;
    Query(cl[x],l,Mid,L,R,y);Query(cr[x],Mid+,r,L,R,y);
}
int main(){
    Read(n);
    for(i=;i<=n;i++)Read(a[i]),Read(b[i]),Read(w[i]),Read(L[i]),Read(R[i]),Read(p[i]),Ans+=w[i]+b[i];
    cnt=(n<<);
    for(i=;i<=n;i++){
        if(i>)Rt[i]=Rt[i-],Query(Rt[i],,INF,L[i],R[i],(i<<)-);
        Update(Rt[i],Rt[i],,,INF,i);
    }
    t=++cnt;
    for(i=;i<=n;i++){
        gjghfd::Add(,i<<,w[i]);
        gjghfd::Add(i<<,t,b[i]);
        gjghfd::Add((i<<)-,i<<,p[i]);
    }
    printf("%d\n",Ans-gjghfd::Dinic());
    return ;
}