概要

周期的に変化する2人の速さをもとに、高橋君が青木君に追い付く最小の整数時刻を求める問題です。クエリによって速さが更新されるため、効率的な再計算と追い付く判定が求められます。

考察

1. 相対速度に着目する

高橋君が座標 \(0\)、青木君が座標 \(d\) からスタートし、時刻 \(t\) において高橋君が青木君に追い付く条件は、「時刻 \(t\) までの高橋君の進んだ距離の合計」\(\ge\)「時刻 \(t\) までの青木君の進んだ距離の合計 \(+ d\)」です。

これを整理すると、各秒ごとの高橋君と青木君の速さの差（相対速度）を \(D_i = B_i - A_i\) としたとき、 $\(\sum_{s=1}^{t} D_{(s-1 \bmod N) + 1} \ge d\)\( を満たす最小の非負整数 \)t$ を探す問題に言い換えられます。

2. 周期性を利用する

時刻 \(t\) を \(N\) で割った商を \(q\)、余りを \(r\) とします（\(t = qN + r\)、ただし \(1 \le r \le N\)）。 \(1\) 周期（\(N\) 秒間）で縮まる距離を \(S_N = \sum_{i=1}^N D_i\)、周期の途中 \(r\) 秒までに縮まる距離を \(S_r = \sum_{i=1}^r D_i\) とすると、時刻 \(t\) までに縮まる合計距離は \(q \cdot S_N + S_r\) と表せます。

3. 追い付く条件の判定

クエリ 2 で与えられる \(d\) に対して、以下の 2 つのケースを考えます。

• \(S_N \le 0\) の場合（1周期で距離が縮まない、または広がる） この場合、時間が経過しても周期ごとに状況が悪化するか変わらないため、最初の 1 周期（\(t=1\) から \(N\)）で追い付けなければ、その後も永遠に追い付けません。

• \(S_N > 0\) の場合（1周期ごとに着実に距離が縮まる） この場合はいつか必ず追い付きます。各 \(r \in \{1, \dots, N\}\) について、 \(q \cdot S_N + S_r \ge d \iff q \cdot S_N \ge d - S_r\) を満たす最小の非負整数 \(q\) を求めます。

  • \(d - S_r \le 0\) ならば \(q = 0\)
  • \(d - S_r > 0\) ならば \(q = \lceil (d - S_r) / S_N \rceil\) こうして得られる \(t = qN + r\) の中で最小のものが答えとなります。

アルゴリズム

1. 初期化:
   • 各秒の相対速度 \(D_i = B_i - A_i\) を計算します。
   • 累積和 \(S_r = \sum_{i=1}^r D_i\) を計算しておきます。
2. クエリ 1 (更新):
   • 指定された \(i\) 番目の \(A_i, B_i\) を更新し、\(D_i\) を再計算します。
   • 累積和 \(S_k\) を \(k=i\) から \(N\) まで再計算します。これは \(O(N)\) で可能です。
3. クエリ 2 (計算):
   • \(S_N \le 0\) ならば、\(S_r \ge d\) となる最小の \(r \in \{1, \dots, N\}\) を探します。なければ \(-1\) です。
   • \(S_N > 0\) ならば、各 \(r \in \{1, \dots, N\}\) に対して必要な周期数 \(q\) を計算し、最小の \(t = qN + r\) を求めます。これは \(O(N)\) で可能です。

計算量

• 時間計算量: \(O(NQ)\)
  • 累積和の更新に \(O(N)\)、追い付く時刻の判定に \(O(N)\) かかります。
  • 制約 \(NQ \le 10^7\) より、この計算量で十分に間に合います。
• 空間計算量: \(O(N)\)
  • 速さや累積和を保持するための配列サイズは \(N\) に依存します。

実装のポイント

• オーバーフローに注意: \(d\) が最大 \(10^{15}\) であり、移動距離も非常に大きくなるため、計算には 64bit 整数型（C++ の long long）を使用してください。

• 切り上げ除算: \(q = \lceil (d - S_r) / S_N \rceil\) の計算は、整数除算を用いて (d - S_r + S_N - 1) / S_N と書くことができます。

• 入出力の高速化: クエリ数が多いため、cin.tie(NULL); ios_base::sync_with_stdio(false); などで入出力を高速化しておくと安全です。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Takahashi and Aoki chase each other on a number line.
 * Speeds change periodically every N seconds.
 * Takahashi catches Aoki if his position is greater than or equal to Aoki's at some integer time t.
 * Let D_i = B_i - A_i be the relative gain Takahashi makes in the i-th second of the cycle.
 * The total gain at time t = qN + r (0 <= r < N) is q * S_N + S_r, where S_k is the prefix sum of D_i.
 */

int main() {
    // Speed up standard I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    // Use long long for all speed and distance calculations to prevent overflow.
    // Coordinates can reach around 3 * 10^18, which fits in a 64-bit signed integer.
    vector<long long> A(N + 1), B(N + 1), D(N + 1), S(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i] >> B[i];
        D[i] = B[i] - A[i];
    }

    // Precompute the gain at each second within the first cycle.
    for (int i = 1; i <= N; ++i) {
        S[i] = S[i - 1] + D[i];
    }

    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            // Update speed and prefix sums for the modified table entry.
            int i;
            long long a, b;
            cin >> i >> a >> b;
            A[i] = a;
            B[i] = b;
            D[i] = B[i] - A[i];
            // Re-calculate prefix sums from index i to N. Complexity: O(N).
            for (int k = i; k <= N; ++k) {
                S[k] = S[k - 1] + D[k];
            }
        } else if (type == 2) {
            long long d;
            cin >> d;
            long long SN = S[N];
            
            // If the total gain per cycle is non-positive, Takahashi must catch Aoki
            // in the first cycle because the gain will not increase in subsequent cycles.
            if (SN <= 0) {
                long long ans = -1;
                for (int r = 1; r <= N; ++r) {
                    if (S[r] >= d) {
                        ans = r;
                        break;
                    }
                }
                cout << ans << "\n";
            } else {
                // If the gain per cycle is positive, Takahashi will always catch Aoki eventually.
                // We iterate through all possible remainders r (1 to N) to find the minimum t = qN + r.
                // Complexity: O(N).
                long long min_t = -1;
                for (int r = 1; r <= N; ++r) {
                    long long qr = 0;
                    if (d > S[r]) {
                        // Calculate the minimum number of full cycles needed to close the gap.
                        // q_r * SN + S_r >= d  =>  q_r * SN >= d - S_r  =>  q_r >= ceil((d - S_r) / SN)
                        qr = (d - S[r] + SN - 1) / SN;
                    }
                    long long tr = qr * N + r;
                    if (min_t == -1 || tr < min_t) {
                        min_t = tr;
                    }
                }
                cout << min_t << "\n";
            }
        }
    }

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。