2019 牛客多校第一场 I、Points Division

平面上给个点的横坐标，纵坐标，a 值，b 值，要求将所有点划分为两个集合，如果在集合A中，那么这个点的值就是a，否则，这个点的值就是b，求将所有点划分之后的所有点值的和的最大值。

对于所有和，都不存在。

-------------------------------------------------------

1、首先分析限制条件，如果对于所有A中的元素，都不在B中所有元素的右下方。

2、那么平面上必然存在一条不减折线，将集合A、B分开，并且集合A中所有点在折线的左上方，集合B所有点在折线的右下方。

3、考虑对于点来说，假设以，为顶点的矩形（不包括点）的所有点划分之后的所有点值的和的最大值已知，那么我们可以考虑将他转移到位置，即将点放在折线上。

4、在每次转移位置的时候，需要同时更新他的左右两个区间，即对于当前转移到的点，更新区间加上，更新区间加上

5、考虑将纵坐标离散化，我们用线段树维护在当前横坐标时，每一个纵坐标在折线上能取到的最大值。

6、对于折线上的点，我们认为他在折线下方，所以在转移状态的时候，为了避免相同横坐标之间的不合法转移，对于横坐标相等的点，我们考虑先对纵坐标大的点进行转移。

7、对于线段树，由于区间，可能出现小于等于0的值，所以考虑离散化的时候将这个数字都加上一个常数，并且建树的时候右端点开大一点。

Code：

#include <bits/stdc++.h>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
const int MAXN = 2e5 + 5;
struct node
{
	int l;
	int r;
	ll maxn;
	ll mark;
}que[MAXN * 4];
int ql, qr, n, m;
ll val;
void up(int k)
{
	que[k].maxn = max(que[k << 1].maxn, que[k << 1 | 1].maxn);
}
void down(int k)
{
	if (que[k].mark)
	{
		que[k << 1].mark += que[k].mark;
		que[k << 1 | 1].mark += que[k].mark;
		que[k << 1].maxn += que[k].mark;
		que[k << 1 | 1].maxn += que[k].mark;
		que[k].mark = 0;
	}
}
void build(int left = 1, int right = n, int k = 1)
{
	que[k].l = left;
	que[k].r = right;
	que[k].maxn = 0;
	que[k].mark = 0;
	if (left == right)
		return;
	imid;
	build(lson);
	build(rson);
}
void updateval(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].maxn += val;
		que[k].mark += val;
		return;
	}
	down(k);
	imid;
	updateval(lson);
	updateval(rson);
	up(k);
}
void updatemax(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].maxn = max(que[k].maxn, val);
		return;
	}
	down(k);
	imid;
	updatemax(lson);
	updatemax(rson);
	up(k);
}
ll query(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return 0;
	if (ql <= left && right <= qr)
		return que[k].maxn;
	down(k);
	imid;
	return max(query(lson), query(rson));
}
struct qq
{
	int x;
	int y;
	int a;
	int b;
}in[MAXN];
int t[MAXN];
int main()
{
	while (scanf("%d", &n) > 0)
	{
		for (int i = 1; i <= n; i++)
		{
			scanf("%d%d%d%d", &in[i].x, &in[i].y, &in[i].a, &in[i].b);
			t[i - 1] = in[i].y;
		}
		sort(t, t + n);
		sort(in + 1, in + 1 + n, [](qq q, qq w) {
			if (q.x != w.x)
				return q.x < w.x;
			return q.y > w.y;
		});
		int cnt = unique(t, t + n) - t;
		for (int i = 1; i <= n; i++)
			in[i].y = lower_bound(t, t + cnt, in[i].y) - t + 2;
		int size = n + 10;
		build(1, size, 1);
		for (int i = 1; i <= n; i++)
		{
			ql = 1, qr = in[i].y;
			ll maxn = query(1, size, 1);
			ql = in[i].y, qr = in[i].y;
			val = maxn + in[i].b;
			updatemax(1, size, 1);
			ql = 1, qr = in[i].y - 1;
			val = in[i].a;
			updateval(1, size, 1);
			ql = in[i].y + 1, qr = size;
			val = in[i].b;
			updateval(1, size, 1);
		}
		printf("%lld\n", que[1].maxn);
	}
}