题解 P6010 【[USACO20JAN] Falling Portals P】

· · 题解

提供一种点凸包的做法。

在我的博客获得更好的阅读体验

考虑两个点 i, j 相遇的时间。
设其为 k，则 a _ i - ik = a _ j - jk \iff a _ i - a _ j = k(i - j) \iff k = \dfrac{a _ i - a _ j}{i - j}。
也就是说相遇时间就是两点之间的斜率。（当然必须是正的）

稍微观察一下就会发现如果要从 i 到 Q _ i 至多经过一个中转点。

经过中转点的要求是：i 到中转点的斜率小于中转点到 Q _ i 的斜率。此时答案为中转点到 Q _ i 的斜率。
只有 4 种情况（蓝色是起点，红色是终点，绿色是中转点）：

1 和 3，2 和 4 本质相同，我们只要处理其中两种，然后将图以原点中心对称再做一遍即可。

我们考虑处理 1 和 4。

对于 1：容易发现中转点是在以 (0, 0) 为左下角，(i, a _ i) 为右上角的矩形中的点。
对于 4：容易发现中转点是在以 (0, 0) 为左下角，(i, a _ {q _ i}) 为右上角的矩形中的点。

也就是我们要实现每次询问一个左下角矩形中的点到某个点（在矩形右上方）的斜率最小值。

考虑没有上边界限制怎么做：单调栈维护上凸壳的前半部分（斜率为正的部分） ，然后二分答案。

有上凸壳限制后，我们考虑维护多个上凸壳，然后每次再对应的上凸壳上二分答案。
对于一个点，如果其可以同时属于多个上凸壳，我们让它属于最上面的那个，这样这些上凸壳就构成了一个森林。
发现询问对应的上凸壳就是矩形内最上方的点所在的上凸壳。

考虑维护这些上凸壳。如果一个点可以同时属于多个上凸壳，我们选择最上方的上凸壳即可。
此时我们惊奇地发现这和询问是等价的。

于是我们一边建树一边处理询问即可。

唯一剩下的问题就是树上二分，这个可以使用倍增解决。

// Think twice, code once.
#include <set>
#include <cmath>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, a[200005], q[200005];
vector<int> b[200005];
struct Frac {
    int p, q;

    Frac() = default;
    Frac(int _p, int _q): p(_p), q(_q) {int g = __gcd(p, q); p /= g, q /= g;}
    bool operator<(const Frac &x) const {return (long long)p * x.q < (long long)x.p * q;}
    bool operator==(const Frac &x) const {return p == x.p && q == x.q;}
} ans[200005];
struct Vect {
    int x, y;

    Vect() = default;
    Vect(int _x, int _y): x(_x), y(_y) {}
    bool operator==(const Vect &a) const {return x == a.x && y == a.y;}
};
int fa[200005][20];
set<pair<int, int>> s;

int binarySearch(int h, Vect now) {
    int st = prev(s.lower_bound({h, 0}))->second;
    for (int i = 17; i >= 0; i--) {
        int to = fa[st][i];
        if (fa[to][0] == 0) continue;
        if (Frac(now.y - a[fa[to][0]], now.x - fa[to][0]) < Frac(now.y - a[to], now.x - to)) st = to;
    }
    if (fa[st][0] && Frac(now.y - a[fa[st][0]], now.x - fa[st][0]) < Frac(now.y - a[st], now.x - st))
        st = fa[st][0];
    // if (now == Vect(2, 11)) printf("%d\n", st);
    return st;
}
void solve(int op) {
    for (int i = 1; i <= n; i++) {
        if (i < q[i] && a[i] < a[q[i]] && !s.empty() && s.begin()->first < a[i]) {
            // if (i == 2) puts("?");
            int p = binarySearch(a[i], Vect(q[i], a[q[i]]));
            ans[!op ? i : n - i + 1] = min(ans[!op ? i : n - i + 1], Frac(a[q[i]] - a[p], q[i] - p));
        }

        for (int j : b[i])
            if(!s.empty() && s.begin()->first < a[j]) {
                // if (j == 2) puts("?");
                int p = binarySearch(a[j], Vect(i, a[i]));
                ans[!op ? j : n - j + 1] = min(ans[!op ? j : n - j + 1], Frac(a[i] - a[p], i - p));
            }

        if (s.empty() || s.begin()->first > a[i]) {s.emplace(a[i], i); continue;}
        fa[i][0] = binarySearch(a[i], Vect(i, a[i]));
        for (int j = 1; j <= 17; j++) fa[i][j] = fa[fa[i][j - 1]][j - 1];
        s.emplace(a[i], i);
    }
    return ;
}

int main() {
    // freopen("world.in", "r", stdin);
    // freopen("world.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &q[i]), ans[i] = Frac(1e9, 1);
        if (i < q[i] && a[i] < a[q[i]]) ans[i] = Frac(a[q[i]] - a[i], q[i] - i);
        if (q[i] < i && a[q[i]] < a[i]) ans[i] = Frac(a[i] - a[q[i]], i - q[i]);
    }

    for (int i = 1; i <= n; i++)
        if (q[i] < i && a[i] < a[q[i]])
            b[q[i]].push_back(i);
    solve(0);

    reverse(a + 1, a + n + 1);
    reverse(q + 1, q + n + 1);
    for (int i = 1; i <= n; i++) a[i] = -a[i], q[i] = n - q[i] + 1, vector<int>().swap(b[i]);
    memset(fa, 0, sizeof(fa));
    set<pair<int, int>>().swap(s);

    for (int i = 1; i <= n; i++)
        if (q[i] < i && a[i] < a[q[i]])
            b[q[i]].push_back(i);
    solve(1);

    for (int i = 1; i <= n; i++)
        if (ans[i].p == 1e9) puts("-1");
        else printf("%d/%d\n", ans[i].p, ans[i].q);
    return 0;
}