bzoj 3218: a + b Problem 最小割+可持久化線段樹

題意：

分析：

感覺上就是一個最小割。。。

把圖建出來之後用可持久化線段樹優化建圖即可。

代碼：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int N=5005;
const int M=300005;
const int inf=1e9;

int n,a[N],b[N],w[N],l[N],r[N],p[N],cnt,s,t,last[M],dis[M],cur[M],sz,ans,tmp[N],root[N];
struct edge{int to,next,c;}e[M*3];
struct tree{int l,r;}tr[M];
queue<int> que;

void addedge(int u,int v,int c)
{
	e[++cnt].to=v;e[cnt].c=c;e[cnt].next=last[u];last[u]=cnt;
	e[++cnt].to=u;e[cnt].c=0;e[cnt].next=last[v];last[v]=cnt;
}

int get(int x)
{
	return x+n*2+1;
}

void build(int d,int l,int r,int x,int y,int z)
{
	if (!d||x>y) return;
	if (l==x&&r==y)
	{
		addedge(get(d),z,inf);return;
	}
	int mid=(l+r)/2;
	build(tr[d].l,l,mid,x,min(y,mid),z);
	build(tr[d].r,mid+1,r,max(x,mid+1),y,z);
}

void ins(int &d,int p,int l,int r,int x,int y)
{
	d=++sz;tr[d]=tr[p];
	if (p) addedge(get(p),get(d),inf);
	if (l==r)
	{
		addedge(y,get(d),inf);return;
	}
	int mid=(l+r)/2;
	if (x<=mid) ins(tr[d].l,tr[p].l,l,mid,x,y),addedge(get(tr[d].l),get(d),inf);
	else ins(tr[d].r,tr[p].r,mid+1,r,x,y),addedge(get(tr[d].r),get(d),inf);
}

bool bfs()
{
	for (int i=0;i<=get(sz);i++) dis[i]=0;
	while (!que.empty()) que.pop();
	dis[s]=1;que.push(s);
	while (!que.empty())
	{
		int u=que.front();que.pop();
		for (int i=last[u];i;i=e[i].next)
			if (e[i].c&&!dis[e[i].to])
			{
				dis[e[i].to]=dis[u]+1;
				if (e[i].to==t) return 1;
				que.push(e[i].to);
			}
	}
	return 0;
}

int dfs(int x,int maxf)
{
	if (x==t||!maxf) return maxf;
	int ret=0;
	for (int &i=cur[x];i;i=e[i].next)
		if (e[i].c&&dis[e[i].to]==dis[x]+1)
		{
			int f=dfs(e[i].to,min(e[i].c,maxf-ret));
			e[i].c-=f;
			e[i^1].c+=f;
			ret+=f;
			if (maxf==ret) break;
		}
	return ret;
}

void dinic()
{
	while (bfs())
	{
		for (int i=0;i<=get(sz);i++) cur[i]=last[i];
		ans-=dfs(s,inf);
	}
}

int main()
{
	scanf("%d",&n);
	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]),ans+=w[i]+b[i];
	s=0;t=1;cnt=1;
	for (int i=1;i<=n;i++) addedge(s,i+1,w[i]),addedge(i+1,t,b[i]),tmp[i]=i+1+n,addedge(tmp[i],i+1,p[i]);
	for (int i=1;i<=n;i++)
	{
		build(root[i-1],0,1e9,l[i],r[i],tmp[i]);
		ins(root[i],root[i-1],0,1e9,a[i],i+1);
	}
	dinic();
	printf("%d",ans);
	return 0;
}