记录编号	365412	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]你猜是不是DP	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	4.292 s
提交时间	2017-01-20 13:52:09	内存使用	57.52 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e6+10;
struct edge{
	int f,t,g,o;
	edge(int F=0,int T=0,int G=0,int O=0){
		f=F;t=T;g=G;o=O;
	}
}w[N];
int n,m,s=0,t=1,P=1,head[N],tail[N],next[N],cnt;
void Add(int f,int t,int g){
	++cnt;w[cnt]=edge(f,t,g,cnt+1);
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	++cnt;w[cnt]=edge(t,f,0,cnt-1);
	if (!head[t]) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}
int a[N],id[N];long long ans;
#define lc x<<1
#define rc (x<<1)|1
struct Segment_tree{
	int pos[N];
	void build(int x,int l,int r,int tp){
		pos[x]=++P;
		if (l==r){
			int v;scanf("%d",&v);
			if (!tp) id[l]=pos[x],a[x]=v;
			else{
				pos[x]=id[l];a[x]-=v;
				ans+=v;
				if (a[x]>0) Add(s,pos[x],a[x]),ans+=a[x];
					else Add(pos[x],t,-a[x]);
			}
			return;
		}
		int mid=(l+r)>>1;
		build(lc,l,mid,tp);
		build(rc,mid+1,r,tp);
		if (!tp) Add(pos[x],pos[lc],1e9),Add(pos[x],pos[rc],1e9);
			else Add(pos[lc],pos[x],1e9),Add(pos[rc],pos[x],1e9);
	}
	void add(int x,int l,int r,int L,int R,int tp){
		if (l>=L&&r<=R){
			if (!tp) Add(P,pos[x],1e9);
				else Add(pos[x],P,1e9);
			return;
		}
		int mid=(l+r)>>1;
		if (R>mid) add(rc,mid+1,r,L,R,tp);
		if (L<=mid) add(lc,l,mid,L,R,tp);
	}
}Black,White;
struct st{
	int x,i,df;
	st(int X=0,int DF=0){x=X;i=head[x];df=DF;}
}z[N];
#define V z[top].x
#define E z[top].i
#define F z[top].df
int l[N],top;
void change(){
	int df=F;ans-=df;
	for (int i=top-1;i;i--){
		w[z[i].i].g-=df;
		w[w[z[i].i].o].g+=df;
		z[i].df-=df;
		if (!z[i].df) top=i;
	}
}
queue<int> Q;
void bfs(){
	for (int i=0;i<=P;i++) l[i]=0;
	l[s]=1;Q.push(s);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		for (int i=head[v];i;i=next[i])
		if (w[i].g&&!l[w[i].t])
			l[w[i].t]=l[v]+1,Q.push(w[i].t);
	}
}
bool dinic(){
	bfs();
	if (!l[t]) return 0;
	z[top=1]=st(s,1e9);
	while (top){
		if (V==t){change();top--;E=next[E];continue;}
		if (!E){l[V]=0;top--;E=next[E];continue;}
		if (w[E].g&&l[w[E].t]==l[V]+1)
			z[top+1]=st(w[E].t,min(F,w[E].g)),top++;
		else E=next[E];
	}
	return 1;
}
int main()
{
	freopen("nicai.in","r",stdin);
	freopen("nicai.out","w",stdout);
	scanf("%d%d",&n,&m);
	Black.build(1,1,n,0);
	White.build(1,1,n,1);
	while (m--){
		int tp,l,r,c;
		scanf("%d%d%d%d",&tp,&l,&r,&c);
		++P;ans+=c;
		if (tp==1) Add(s,P,c),Black.add(1,1,n,l,r,0);
			else Add(P,t,c),White.add(1,1,n,l,r,1);
	}
	while (dinic());
	printf("%lld\n",ans);
	return 0;
}