题目描述

给定 个二维平面上的点，每个点有权值 和 。

将点集划分为两个集合，满足任意 A 集合的点 和 B 集合点 ，要么 ，要么 。

A 集合的点使用权值 ，B 集合的点使用权值 ，求最大化权值和。

分析

题目即是用一个阶梯型的分段函数将点集划分为两块，A 集合在左上，B 集合在右下，边界上的点属于 B 集合。

从左至右扫描线，线段树维护分界线右端点纵坐标为 时的最大权值和 。

对于一个点 ，如果他作为分界线的转折点，肯定是从底线一条权值最大的分界线转移过来，即 （纵坐标由上至下排序，消除重复计算）。

对于高度大于 的分界线端点，他一定会取到点 ，即区间加上权值 。

对于高度小于 的分界线端点，他一定不会取到点 ，即区间权值加上 。

最后，答案为全局最大值。