记录编号	371789	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]你猜是不是DP	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	2.125 s
提交时间	2017-02-16 21:01:41	内存使用	1.23 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 40005, inf = 0x3f3f3f3f;
struct Edge {
	int next, to, cap, flow;
	Edge(int a=0, int b=0, int c=0) :
		next(a), to(b), cap(c), flow(0) {}
}; 
vector<Edge> e(2);
int head[maxn];
void Add(int u, int v, int c) {
	e.push_back(Edge(head[u], v, c)); head[u] = e.size()-1;
	e.push_back(Edge(head[v], u, 0)); head[v] = e.size()-1;
}
int N, M;
int root1, root2, lc[maxn], rc[maxn], p_, le, ri;

void link1(int u, int v, int c) { Add(u, v, c); } 
void link2(int u, int v, int c) { Add(v, u, c); }
void build(int l, int r, int &x, void (*link)(int,int,int)) {
	if(l==r) { x = l; return; }
	if(!x) x = ++p_;
	int mid = (l+r)>>1;
	build(l, mid, lc[x], link);
	build(mid+1, r, rc[x], link);
	link(x, lc[x], inf);
	link(x, rc[x], inf);
}
void cover(int l, int r, int x, void (*link)(int,int,int)) {
	if(le<=l && r<=ri) 
		{ link(p_, x, inf); return; }
	int mid = (l+r)>>1;
	if(le<=mid) cover(l, mid, lc[x], link);
	if(ri>mid) cover(mid+1, r, rc[x], link);
}

#define src (N+1)
#define sink (N+2)
int d[maxn], cur[maxn], vis[maxn], T;
queue<int> q;
bool bfs() {
	vis[src] = ++T; q.push(src);
	while(!q.empty()) {
		int x = q.front(); q.pop();
		for(int i=head[x]; i; i=e[i].next) {
			int to = e[i].to;
			if(vis[to]!=T && e[i].cap>e[i].flow) {
				vis[to] = T;
				d[to] = d[x]+1;
				q.push(to);
			}
		}
	}
	return vis[sink]==T;
}
int dfs(int x, int a) {
	if(x==sink || !a) return a;
	int flow = 0, f;
	for(int &i=cur[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(d[to]==d[x]+1 && (f=dfs(to, min(a, e[i].cap-e[i].flow)))>0) {
			e[i].flow += f;
			e[i^1].flow -= f;
			flow += f;
			a -= f;
			if(!a) break;
		}
	}
	return flow;
}
int dinic() {
	int flow = 0;
	while(bfs()) {
		memcpy(cur, head, sizeof cur);
		flow += dfs(src, inf);
	} return flow;
}

int main() {
	freopen("nicai.in","r",stdin);
	freopen("nicai.out","w",stdout);
	scanf("%d%d", &N, &M);
	p_ = N+2;
	build(1, N, root1, link1); // black
	build(1, N, root2, link2);
	int sum = 0;
	for(int i=1, v; i<=N; ++i) {
		scanf("%d", &v);
		if(v>0) sum += v, Add(src, i, v); 
		else Add(i, sink, -v);
	}
	for(int i=1, v; i<=N; ++i) {
		scanf("%d", &v);
		if(v>0) sum += v, Add(i, sink, v); 
		else Add(src, i, -v);

	}
	int op, l, r, v;
	while(M--) {
		scanf("%d%d%d%d", &op, &l, &r, &v);
		sum += v;
		le = l, ri = r;
		if(op==1) {
			Add(src, ++p_, v);
			cover(1, N, root1, link1);
		} else {
			Add(++p_, sink, v);
			cover(1, N, root2, link2);
		}
	}
	printf("%d\n", sum-dinic());
	getchar(), getchar();
	return 0;
}