[UOJ#77]A+B Problem

可持久化线段树优化连边。。。
发现连线段树优化连边都没有在正式比赛考过。。。
网络流建模
问题转化成(sum (Bi+Wi) -sum_{黑点}Wi-sum_{白点}Bi-sum_{奇怪的点}Pi)
S->i连一条容量为Bi的边，表示选白色，i->T连条容量为Wi的边，i->i'连容量Pi的边，i'->会因它变得奇怪的点 连inf，当i为白色时，如果对应点选黑色，一定花Pi才能割开。
求最小割即可。因为强制j<i因此强行可持久化。。。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N=300005,inf=2100000000;
struct Edge{int to,nxt,val;}e[N*10];
int ls[N],rs[N],val[N],sum[N],a[5005],b[5005],w[5005],l[5005],r[5005],p[5005],n,tmp,c[5005*3],ans,head[N],ecnt=1,tot,cur[N],S,T;
void ins(int bg,int ed,int val) {
    e[++ecnt].to=ed;
    e[ecnt].nxt=head[bg];
    e[ecnt].val=val;
    head[bg]=ecnt;
}
void add(int a,int b,int c) {
	ins(a,b,c);ins(b,a,0);
}
void ins(int k,int l,int r,int ql,int qr,int id) {
	if(!k) return;
	int mid=l+r>>1;
	if(ql<=l&&r<=qr) {add(id,k,inf);return;}
	if(ql<=mid) ins(ls[k],l,mid,ql,qr,id);
	if(mid+1<=qr) ins(rs[k],mid+1,r,ql,qr,id);
}
void update(int &k,int l,int r,int val,int id) {
	ls[++tot]=ls[k],rs[tot]=rs[k];
	int mid=l+r>>1;
	if(l==r) {
		if(k) add(tot,k,inf);
		add(tot,id,inf);
		k=tot;return;
	}
	k=tot;
	if(val<=mid) update(ls[k],l,mid,val,id);
	else update(rs[k],mid+1,r,val,id);
}

int h[N];
queue<int>q;
bool bfs() {
    memset(h,-1,sizeof h);
    q.push(S);
    h[S]=0;
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        for(int i=head[x]; i; i=e[i].nxt) {
            if(e[i].val&&h[e[i].to]==-1) {
                h[e[i].to]=h[x]+1;
                q.push(e[i].to);
            }
        }
    }
    return h[T]!=-1;
}
int dfs(int x,int f) {
    if(x==T)return f;
    int tp,used=0;
    for(int i=cur[x]; i; i=e[i].nxt) {
        if(e[i].val&&h[e[i].to]==h[x]+1) {
            tp=dfs(e[i].to,min(e[i].val,f-used));
            e[i].val-=tp;
            if(e[i].val)cur[x]=i;
            e[i^1].val+=tp;
            used+=tp;
            if(used==f)return f;
        }
    }
    if(!used)h[x]=-1;
    return used;
}
void dinic() {
    while(bfs()) {
        memcpy(cur,head,sizeof head);
        ans-=dfs(S,inf);
    }
}
int main() {
	scanf("%d",&n);S=n+n+1,T=n+n+2;
	for(int i=1;i<=n;i++) 
	scanf("%d%d%d%d%d%d",&a[i],&b[i],&w[i],&l[i],&r[i],&p[i]),
	c[++tmp]=a[i],c[++tmp]=l[i],c[++tmp]=r[i],ans+=b[i]+w[i];
	sort(c+1,c+1+tmp);
	int u=unique(c+1,c+1+tmp)-c-1;
	for(int i=1;i<=n;i++) {
		add(S,i,b[i]),add(i,T,w[i]),add(i,i+n,p[i]);
		a[i]=lower_bound(c+1,c+1+u,a[i])-c;
		l[i]=lower_bound(c+1,c+1+u,l[i])-c;
		r[i]=lower_bound(c+1,c+1+u,r[i])-c;
	}
	tot=n+n+2;
	for(int i=1,rt=0;i<=n;i++) {
		ins(rt,1,u,l[i],r[i],i+n);
		update(rt,1,u,a[i],i);
	}
	for(int i=n+n+3;i<=tot;i++) {
		if(ls[i]) add(i,ls[i],inf);
		if(rs[i]) add(i,rs[i],inf);
	}
	dinic();
	cout<<ans;
}