2024.3.4
A.「ROI 2017 Day 2」学习轨迹
题面：
给定两个二元组序列 \text{A} 和 \text{B}，每个二元组表示这个位置的数的编号与价值。
可以对于两个序列各选取一个区间（可以为空），使得两个区间中的数的编号不重复出现，要求在满足该条件的情况下，区间的价值和最大。
思路
首先来考虑最劣解是什么情况，可以发现最劣的情况是全选其中一个序列，另一个序列不选。
所以在分别进行区间选取的时候，一定有一个序列选取的区间里值的总和大于该序列中和的一半。
因为如果两个序列选取区间的取值和都不足该序列总和的一半，全选某个区间一定是更优的。
那先假定序列 \text{A} 选取的和超过一半，那其实可以得到一个必选的点。
假设这个点为 \text{p}，那么 \text{p} 需要满足的条件就是 \text{p} 的前缀和大于总和的一半， \text{p} 的后缀和大于总和的一半，这样，不管怎么选，\text{p} 一定会被选中，具体地说，\text{p} 就是前缀和第一个大于总和的一半的位置。
接下来考虑另一个序列 \text{B} 对序列 \text{A} 的影响。
可以发现，如果每次选择一个 \text{B} 中的值，如果这个值在 \text{A} 中出现过，那么一定可以确定一个 \text{A} 所选取的区间的左端点大于某个数或者右端点小于某个数。
原因是显然的，因为在 \text{B} 中选了的数在这 \text{A} 中一定不能再选了，所以自然可以为 \text{A} 确定一个范围。
性质的分析差不多结束了，那么接下来就可以考虑如何求解了。
可以考虑枚举 \text{B} 序列选择的右端点，然后使用个什么东西维护对于该右端点的最大值。
但具体该怎么维护呢？
想到 \text{A} 序列中存在一个必须选的点，那么可以根据类似分治的思想，以这个点为界限，分成左右两个部分考虑。
对于每个新枚举到的 \text{B} 序列中的数，如果在 \text{p} 的左边，那么在这个数之前的 \text{A} 序列的和都要删除，如果在 \text{p} 的右边，那么在这个数之后的 \text{A} 序列的和都要删除。
显然可以使用一个递增的单调栈进行维护，每次加入的时候，先把栈中比这个数位置考前的贡献全部删掉，然后加入这个点的贡献。
贡献的改变可以使用一颗线段树进行维护，注意有点小技巧，在维护的过程中，不单只维护 \text{A} 的值，同时需要把 \text{B} 的区间贡献通过前缀和拆成两部分，把减掉的部分加入线段树中一起维护，加的那部分在枚举的时候直接加上就行，这样才能保证和是最优的。
最后把 \text{A}，\text{B} 序列交换再处理一遍即可。
时间复杂度： O(n \log n)
标签：报告,text,选取,2024,序列,解题,端点,区间,维护 From： https://www.cnblogs.com/Populus-euphratica/p/18051521