AT_arc129_b Range Point Distance

简要题意

给定 对 ，然后在每次给出后都要选一个 使得 到之前给出的所有区间的距离 的最大值最小。一个 到区间 的距离定义为 。

策略分析

既然我们每次都要输出答案，那我们不妨从 的定义入手，我们发现在这个定义中，当其结果不为 时只有两种情况，要么 在 右边，要么 在 左边。那么我们考虑现在有一堆区间，因为我们求的是 到所有区间距离的最大值，所以其实我们需要关心的，能够对我们答案造成影响的值就是最靠右的 和最靠左的 。得到这个结论后剩下的就比较简单了，我们只需要每次输入一个区间都更新一下这个关键的 和 即可。

我们现在知道了能够对我们答案造成影响的两个关键点，那么答案如何求解呢，我们进行分类讨论。

  • 当 时，意味着之前输入的所有区间都有一个共同的交集 ，这个结论直接从 的定义得出，那么我们随便在 里怎么选都是 ，所以要找的最小值就是 。
  • 当 时，以 为左端点的区间和以 为右端点的区间一定是之前输入的所有区间里距离最远的一组，只有这一对区间才会产生到 的最大值。那么这个最大值最小当且仅当 取在 正中间，又因为要去最大值所以此时 。

分析出这两条以后直接在线做就好了，时间复杂度是线性的。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;

namespace SHAWN {
    const LL INF = 1e9 + 7;
    LL n, sl = -INF, sr = INF;
    signed work()
    {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            LL l, r; cin >> l >> r;
            sl = max(sl, l), sr = min(sr, r);
            // 更新两个关键点
            if (sr >= sl) { cout << "0\n"; }
            else cout << ((sl - sr + 1) >> 1) << '\n';
            // 按照刚刚的分类讨论进行输出
        }
        return 0;
    }
}

signed main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}