//
//  main.cpp
//  T352203 塔台超频 (Hard Version)1
//
//  Created by SkyWave Sun on 2023/7/14.
//

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
#define N (int)5e5 + 1
#define MAXB 20 + 1
ll a[N], b[N];
int n;
int maxxPos[N];
int maxx[MAXB][N];
int lg[N];
void init() {
    for (int i = 1; i < MAXB; ++i) {
        for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
            maxx[i][j] = max(maxx[i - 1][j], maxx[i - 1][j + (1 << (i - 1))]);
        }
    }
}
int query(int l, int r) {
    int len = lg[r - l + 1];
    return max(maxx[len][l], maxx[len][r - (1 << len) + 1]);
}
bool check(ll add) {
    for (int i = 1; i <= n; ++i) {
        int l = i, r = n;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (a[mid] > a[i] + b[i] + add) {
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        maxxPos[i] = r;
        maxx[0][i] = maxxPos[i];
    }
    init();
    int pos = 1;
    while (true) {
        int ans = query(pos, maxxPos[pos]);
        if (pos == ans) {
            return false;
        }
        pos = ans;
        if (a[pos] + b[pos] + add >= a[n]) {
            return true;
        }
    }
}
int main(int argc, const char * argv[]) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld%lld", &a[i], &b[i]);
    }
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) {
        lg[i] = lg[i >> 1] + 1;
    }
    ll l = 0, r = 1e9;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid - 1;
        }else {
            l = mid + 1;
        }
    }
    printf("%lld\n", l);
    return 0;
}

感觉我码风还是非常易于理解的，大家读到这里应该已经了明白了我的做法。

显然 k 具有单调性，马上想到二分。本来想要二分然后加上 bfs 的，但是发现建图根本时间复杂度不够。后来比赛到 1:40 感觉再不猜做法没机会了，于是就想了二分套二分 + 倍增的做法。

首先二分 k，check 函数这样写：

因为 a 数组单调，我们就可以对于每一个点二分求出最远它能覆盖到的点。再用 st 表维护一个点到它最远能覆盖到的点这一区间能跳到的最远的点。

然后在 st 表上类似倍增跳跃。每次跳到区间内能跳到最远的点。如果最远的点还是自己，说明不可达，返回。

否则就一直跳，直到区间内覆盖 n 为止。

时间复杂度大常数 $n \log^2 n$

交了一发，WA 了。想了想，突然紧张地发现做法假了。区间内能跳的远的不一定能跳得下去，可能就在这里卡住了。但事已至此，想其它做法肯定来不及了。又想到出题人可能也想到了这一点，故意造数据来卡。那么很可能卡在了最后一个点，也就是说我们可以冒险的取最后一个点的前几个点，可能能避免被卡掉

于是将倍增跳的第一句（第 48 行）右端点改成取不到的闭区间：

int ans = query(pos, maxxPos[pos - 1]);

当时还没想着能过，寻思着应该多往前查几个，但绿油油的一片还是 AC 了。

当时还寻思着 C 出得那么难怎么那么多人 AC 的，肯定是我做法做繁了。5e5 也不像给想给两个 log 的样子。

所以，数据严重过水，并且求一下正确做法？脑子要炸了。