写在前面
啊因为这段时间一直很忙,所以好久没有更新博客了。
这次正好在校队训练的时候做掉了这个非常具有启发意义的题目,所以写上来分享一下。
题目
题目大意:维护一个数列,支持区间加,区间减,查询某个位置的历史绝对值最大值。
做法
历史绝对值最大值,可以通过维护最大值和最小值来解决,下面我们仅考虑最大值,最小值同理。
这是一个很好的扫描线的题目,一般而言,对于区间修改,单点查询的可离线题目,我们可以通过扫描线解决。
先离线所有操作,然后考虑在区间的左端点加入这个操作,右端点删除这个操作。
我们考虑该操作对区间内的贡献,每个操作对应了时间线段树上的一个位置,那么每个时刻该扫描线位置的历史值对应了时间区间上的一个前缀和。
那么我们考虑直接维护这个前缀和,任意时刻加入删除一个数的操作可以看成对时间区间的区间加和区间减,同时我们维护时间区间的每个点的最大值即可。
这样对于每个查询对应的时间,我们查询在这个时间点之前的时间区间内的最大值即可,用支持区间修改的线段树即可维护。
代码
1 |
|