记录编号	363906	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]你猜是不是DP	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	1.590 s
提交时间	2017-01-14 09:28:44	内存使用	23.66 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
#define ex(x) ( (x&1) ? x+1 : x-1 )
const int maxn=90000;
struct Edge{
	int next,to,flow;
}e[maxn*20];
int len,head[maxn],cur[maxn];
int n,m,start,end,ansflow,deep[maxn];
void Insert(int x,int y,int flow){
	len++;e[len].to=y;e[len].next=head[x];
	head[x]=len;e[len].flow=flow;
}
void Add_edge(int x,int y,int flow){
	Insert(x,y,flow);Insert(y,x,0);
}
int cnt,id[maxn],a[maxn],tot;
struct Segment_Tree{
	int pos[maxn];
	#define lson rt<<1,l,mid
	#define rson rt<<1|1,mid+1,r
	void Build(int rt,int l,int r,int type){
		pos[rt]=++cnt;
		if(l==r){
			int valu;scanf("%d",&valu);
			if(type==0){
				id[l]=pos[rt];a[rt]=valu;
			}
			else {
				pos[rt]=id[l];a[rt]-=valu;
				tot+=valu;
				if(a[rt]>0)Add_edge(start,pos[rt],a[rt]),tot+=a[rt];
				else Add_edge(pos[rt],end,-a[rt]);
			}
			return;
		}
		int mid=(l+r)>>1;
		Build(lson,type);Build(rson,type);
		if(!type){
			Add_edge(pos[rt],pos[rt<<1],Inf);
			Add_edge(pos[rt],pos[rt<<1|1],Inf);
		}
		else {
			Add_edge(pos[rt<<1],pos[rt],Inf);
			Add_edge(pos[rt<<1|1],pos[rt],Inf);
		}
	}
	void add(int s,int t,int rt,int l,int r,int type){
		if(s<=l && t>=r){
			if(type==0)Add_edge(cnt,pos[rt],Inf);
			else Add_edge(pos[rt],cnt,Inf);
			return;
		}
		int mid=(l+r)>>1;
		if(s<=mid)add(s,t,lson,type);
		if(t>mid)add(s,t,rson,type);
	}
}Black,White;
int Head,Tail,q[maxn];
bool Bfs(){
	Head=Tail=0;q[Tail++]=start;
	memset(deep,-1,sizeof(deep));deep[start]=1;
	while(Head^Tail){
		int k=q[Head++];
		for(int i=head[k];i;i=e[i].next){
			int j=e[i].to;
			if(deep[j]<0 && e[i].flow>0){
				deep[j]=deep[k]+1;
				q[Tail++]=j;
			}
		}
	}
	//printf("%d ",deep[end]);
	if(deep[end]<0)return false;
	return true;
}
int Dfs(int x,int flow){
	if(x==end || !flow)return flow;
	int tot=0;
	for(int &i=cur[x];i && flow;i=e[i].next){
		int j=e[i].to;
		if(e[i].flow>0 && deep[j]==deep[x]+1){
			int dd=Dfs(j,min(e[i].flow,flow));
			e[i].flow-=dd;e[ex(i)].flow+=dd;
			flow-=dd;tot+=dd;
			if(!flow)break;
		}
	}
	return tot;
}
void Maxflow(){
	while(Bfs()){
		memcpy(cur,head,sizeof(head));
		ansflow+=Dfs(start,Inf);
	}
}
void Init();
int main(){
	freopen("nicai.in","r",stdin);freopen("nicai.out","w",stdout);
	Init();
	getchar();getchar();
	return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	start=maxn-10;end=start+1;
	Black.Build(1,1,n,0);
	White.Build(1,1,n,1);

	for(int i=1;i<=m;i++){
		int type,l,r,valu;scanf("%d%d%d%d",&type,&l,&r,&valu);
		cnt++;tot+=valu;
		if(type==1){
			Add_edge(start,cnt,valu);
			Black.add(l,r,1,1,n,0);
		}
		else {
			Add_edge(cnt,end,valu);
			White.add(l,r,1,1,n,1);
		}
	}
	Maxflow();
	printf("%d\n",tot-ansflow);
}