TIOJ 1958：[IOI 2016] Shortcut

TIOJ 1958：[IOI 2016] Shortcut

題目大意：有 $n$ 站火車站，第 $i$ 站和 $i+1$ 站距離 $l_i$，第 $i$ 站有一個長度為 $d_i$ 的支線，可以選兩站設一條長度為 $c$ 的通道，令直徑為任兩站最小距離的最大值，問直徑最小可以是多少。

解法：二分搜直徑 $k$，令 $x_i$ 是第 $i$ 個車站的位置，$l,r$ 是設通道的位置，這個直徑是合法的若且唯若對所有 $i<j$，滿足 $d_i+d_j-x_i+x_j\leq k$ 或 $d_i+d_j+|x_i-l|+|x_j-r|+c\leq k$，也就是走原本的路就合法或是要走通道才合法。

在走原本的路不合法的情況下，這五個式子會成立：

$(x_i-d_i)<(x_j+d_j)-k$ 
$r+l\geq (x_j+d_j)+(x_i+d_i)-k+c=A$
$r+l\leq (x_j-d_j)+(x_i-d_i)+k-c=B$
$r-l\geq (x_j+d_j)-(x_i-d_i)-k+c=C$
$r-l\leq (x_j-d_j)-(x_i+d_i)+k-c=D$

找到最大的 $A,C$、最小的 $B,D$ 後，就可以去枚舉 $l$，看 $r$ 有沒有解，發現在 $j$ 固定的情況下，$x_i+d_i$ 要越大越好，$x_i-d_i$ 要越小越好。

對於 $B,C$，因為要最小的 $x_i-d_i$，所以只要檢查目前最小的 $x_i-d_i$ 有沒有滿足第一個式子就好。

對於 $A$，當 $x_j+d_j$ 比之前的小時，最大的 $x_i+d_i$ 有可能不會滿足第一式，但因為之前的 $x_j+d_j$ 更大，所以就算在這次更新 $A$，$A$ 也不會變大。

對於 $D$，當 $x_j+d_j$ 比之前的小時，最大的 $x_i+d_i$ 有可能不會滿足第一式，但因為 $x_j$ 是遞增的，如果 $x_j+d_j$ 變小，代表 $d_j$ 變小，$x_j-d_j$ 會變大，$D$ 不會改變。

可以用一個 $\text{deque}$ 維護還沒取的 $x_i+d_i$，每次詢問 $k$ 會花 $O(n)$，複雜度共 $O(n\log C)$。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "lib1958.h"
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const ll INF = 1e18;
const int SIZE = 1e6 + 5;

int n, c;
ll x[SIZE];
int d[SIZE];

bool ok(ll k) {
    ll A, B, C, D, mn, mx;
    A = C = mx = -INF;
    B = D = mn = INF;
    deque<pair<ll, ll>> st;
    FOR (i, 1, n) {
        if (mn < x[i] + d[i] - k) {
            B = min(B, x[i] - d[i] + mn + k - c);
            C = max(C, x[i] + d[i] - mn - k + c);
        }
        while (st.size() && st[0].F < x[i] + d[i] - k) {
            mx = max(mx, st[0].S);
            st.pop_front();
        }
        A = max(A, x[i] + d[i] + mx - k + c);
        D = min(D, x[i] - d[i] - mx + k - c);
        mn = min(mn, x[i] - d[i]);
        while (st.size() && x[i] - d[i] <= st.back().F && x[i] + d[i] >= st.back().S) st.pop_back();
        if (!st.size() || x[i] + d[i] > st.back().S) st.pb(x[i] - d[i], x[i] + d[i]);
    }
    if (A > B || C > D) return 0;
    int l1 = n + 1, r1 = n, l2 = 1, r2 = 0;
    FOR (i, 1, n) {
        while (l1 > 1 && A - x[i] <= x[l1 - 1]) l1--;
        while (r1 >= 1 && x[r1] > B - x[i]) r1--;
        while (l2 <= n && C + x[i] > x[l2]) l2++;
        while (r2 < n && x[r2 + 1] <= D + x[i]) r2++;
        if (max(l1, l2) <= min(r1, r2)) return 1;
    }
    return 0;
}

ll find_shortcut(int _n, int _l[], int _d[], int _c) {
    n = _n, c = _c;
    FOR (i, 0, n - 1) {
        if (i >= 1) x[i + 1] = x[i] + _l[i - 1];
        d[i + 1] = _d[i];
    }
    ll l = 0, r = 0, mx = -INF;
    FOR (i, 1, n) {
        r = max(r, d[i] + x[i] + mx);
        mx = max(mx, d[i] - x[i]);
    }
    while (l < r) {
        ll mid = (l + r) / 2;
        if (ok(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！