Target Practice II (USACO Silver 2024 February)

此题算法难度不大，但是思路比较偏，特别是不容易想到上边界和下边界是分开算的，所以认为具有蓝题难度（浴谷标绿）。

每个矩形 target 在时间 $i$ 时单独出现（ $(x, y)$ 坐标都大于等于 $1$ ），四头牛都在 $y$ 轴上向四个角分别射击，如果子弹进入矩形内部就失败。问在不失败的情况下，最上方牛到最下方牛之间的最小距离是多少。目标数量 $N < 4 \times 10^4$ 。
牛 $c$ 的坐标与目标点和斜率的关系： $y_c = y - \text{slope} \times x$ 。
唯一会失败的情况，是矩形的右上角和右下角，如果 $\text{slope} > 0$ 射击右上角，或者 $\text{slope} < 0$ 射击右下角，都会失败。所以问题就转化成：在右侧两个端点的斜率有正负限制的情况下，求所有 $y_c$ 的最小范围， $N < 4 \times 10^4$ 。
考虑目标的左边界上的点， $y$ 从小到大，应该匹配从小到大的斜率，这样才能使得范围最小。
所以结合上面 3 和 4，我们可以检查完全不合法的情况（没有足够的正或者负的斜率），然后唯一确定每个点的斜率的符号。这个是这个题最大的难点，要从正和负分开的情况来考虑，本质上是把题分成了两部分。用 $\text{slope}>0$ 的点来计算 $y_{\min}$ ，用 $\text{slope}<0$ 的点来计算 $y_{\max}$ ，然后求两个 $y_{\min}$ 和 $y_{\max}$ 之间的差值。
然后不失一般性考虑 $\text{slope}>0$ 的半个问题，求极值应该可以想到二分答案（因为斜率是整数，所以 $y$ 坐标也都是整数）。怎么 check 一个答案是否合法呢？对于每个点，用最大的能满足要求的斜率（用 multiset 来查询），这样就可以 $O(N \log N)$ 地完整检查，这样整个的复杂度就是 $O(n \log^2 n)$ 。
另半个问题，可以重新实现一遍，也可以如下面代码这样，转化为正slope的问题来解：就是把所有y都取相反数，把slope也取相反数，这样就可以重用实现，最后把结果y也取反。

以下是第一个例子的正负slope分布图（*表示目标区域，+表示slope为正的点，-表示slope为负的点）：

y
6 + * -
5 * * *
4 + * +
3 - * * * * -
2 * * * * * *
1 - * * * * +
0 1 2 3 4 5 6 x

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int t,n,x1;
int y1[40005], y2[40005], x2[40005];
int s[160005];
 
bool check(vector<pi> &pts, vector<int> &slopes, long long y) {
    multiset<int> ss;
    for (auto s: slopes)
        ss.insert(s);
    for (auto p: pts) {
        long long s0 = (p.second - y) / p.first;
        // find the largest slope in slopes <= s0
        auto it = ss.lower_bound(s0);
        if (it == ss.end() || *it > s0) {
            if (it == ss.begin()) return false;
            it--;
        }
        ss.erase(it);
    }
    return true;
}
 
// maximize the minimum y for all x axis points going to pts with positive slopes
ll solve(vector<pi> &pts, vector<int> &slopes) {
    int n = pts.size();
    long long l = -1e18, r = 1e18;
    while (l < r) {
        long long mid = (l+r+1)/2;
        if (check(pts, slopes, mid)) l = mid;
        else r = mid-1;
    }
    return l;
}
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &x1);
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d", &y1[i], &y2[i], &x2[i]);
        }
        int pos_cnt = 0;
        for (int i = 0; i < 4*n; i++) {
            scanf("%d", &s[i]);
        }
        sort(s, s+4*n);
 
        // sort points and slopes into positive and negative halves
        vector<pi> pts[2];       // 0: postive slope points, 1: negative
        vector<int> slopes[2];
        for (int i = 0; i < 4*n; i++) {
            if (s[i] > 0) {
                pos_cnt++;
                slopes[0].push_back(s[i]);
            } else {
                slopes[1].push_back(-s[i]);
            }
        }
        if (pos_cnt < n || 4*n - pos_cnt < n) {  // at least n positive and n negative slopes for top-right and bottom-right corners
            printf("-1\n");
            continue;
        }
        for (int i = 0; i < n; i++) {    // top-right and bottom-right
            pts[0].push_back({x2[i], y1[i]});
            pts[1].push_back({x2[i], -y2[i]});
        }
        vector<int> y_all;
        for (int i = 0; i < n; i++) {
            y_all.push_back(y1[i]);
            y_all.push_back(y2[i]);
        }
        sort(y_all.begin(), y_all.end());
        for (auto y: y_all) {
            if (pts[1].size() < 4*n-pos_cnt)  // go to negative half first
                pts[1].push_back({x1, -y});
            else
                pts[0].push_back({x1, y});
        }
 
        // top half (negative slope), this part has slope and y reversed, so we negate the result
        long long ans = -solve(pts[1], slopes[1])    
                        - solve(pts[0], slopes[0]) ;
        printf("%lld\n", ans);
    }
 
    return 0;
}