题解归档 - cf406D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf406D
• 本地来源：problems/cf406D/idea.md
• 题目链接：https://codeforces.com/contest/406/problem/D
• 原始标题：cf406D - Hill Climbing

思路

cf406D - Hill Climbing

A climber always moves to the rightmost visible hill. Therefore every hill has a single outgoing next, and each query asks for the first common vertex of two increasing paths, i.e. LCA in the tree with parent next[i].

For i<j, hill j is visible from i iff for every k in between, slope(i,k) < slope(i,j). Thus the rightmost visible hill is the first position where the maximum slope from i to the suffix is achieved. Maintain the upper hull of suffix points from right to left; query the tangent / maximum slope by binary search, with equal slopes choosing the leftmost point to avoid a segment touching an intermediate hill.

代码

来源：problems/cf406D/solution.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const int L = 20;

int n, m;
long long x[N], y[N];
int up[L][N], dep[N];
vector<int> hull;

__int128 cross(int a, int b, int c) {
    return (__int128)(x[b] - x[a]) * (y[c] - y[a]) - (__int128)(y[b] - y[a]) * (x[c] - x[a]);
}

bool less_slope(int p, int a, int b) {
    return (__int128)(y[a] - y[p]) * (x[b] - x[p]) < (__int128)(y[b] - y[p]) * (x[a] - x[p]);
}

int query_next(int p) {
    int l = 0, r = (int)hull.size() - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        int a = hull[(int)hull.size() - 1 - mid];
        int b = hull[(int)hull.size() - 2 - mid];
        if (less_slope(p, a, b)) l = mid + 1;
        else r = mid;
    }
    return hull[(int)hull.size() - 1 - l];
}

void add_hull(int p) {
    hull.push_back(p);
    while ((int)hull.size() >= 3) {
        int a = hull[(int)hull.size() - 1];
        int b = hull[(int)hull.size() - 2];
        int c = hull[(int)hull.size() - 3];
        if (cross(a, b, c) > 0) hull.erase(hull.end() - 2);
        else break;
    }
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    int d = dep[a] - dep[b];
    for (int i = 0; i < L; i++) if (d >> i & 1) a = up[i][a];
    if (a == b) return a;
    for (int i = L - 1; i >= 0; i--) {
        if (up[i][a] != up[i][b]) {
            a = up[i][a];
            b = up[i][b];
        }
    }
    return up[0][a];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];

    up[0][n] = n;
    add_hull(n);
    for (int i = n - 1; i >= 1; i--) {
        up[0][i] = query_next(i);
        dep[i] = dep[up[0][i]] + 1;
        add_hull(i);
    }
    for (int j = 1; j < L; j++) {
        for (int i = 1; i <= n; i++) up[j][i] = up[j - 1][up[j - 1][i]];
    }

    cin >> m;
    for (int i = 1, a, b; i <= m; i++) {
        cin >> a >> b;
        cout << lca(a, b) << " \n"[i == m];
    }
    return 0;
}