luogu1973

题目描述

给出个区间，要将他们分成两部分，要求这两部分之间互不相交，而每部分内部区间可以相交。

求使得区间数较小的部分的最大区间数，以及在每个部分必须被选择情况下的答案。

解题思路

本题的状态很明显，肯定是从时间、选中的个数、区间序号中选择状态。我们记表示时刻之前部分1的区间数为时部分2的区间数。

考虑状态转移，我们不妨枚举转移而来的端点，答案为

时间复杂度为。

接下来我们考虑如何选定一个区间求答案。因为我们的状态转移方程与区间的编号没有任何关系，所以我们应该聚焦于其区间信息如何贡献答案。

我们记表示从时刻往后，部分1的区间数为的答案。类比给出状态转移方程，记为最大时间：

那么每一个区间必选且选择的值贡献给部分1的答案应该为

这样枚举得到答案的时间复杂度为。

注意到随着增大而减小，随着增大而减小。

于是先考虑固定，我们使得增大，则可以发现，这个函数是一个上凸函数。

假设对于一个固定的我们求得了一个最大值点，对于而言，必然有，且，又因为，则明显此时有，的最大值点必然在左侧。因此我们可以发现，当单调递增时，最大值点的是单调递减的，因此我们只需要动态维护一个值即可，这样时间复杂度就会被压缩为。

注意：在本题中，f_{i, j}和uf_{i, j}均需要挖掉某些值为-1的点之后才能保证单调性。