概要

「1秒ごとの差分速度」\(C_i = B_i - A_i\) を見ると、追い付く条件は「累積和が初期距離 \(d\) 以上になる最小時刻」を探す問題になります。
周期性を使って「何周期進めば届くか」を先に計算し、最後に周期内を線形探索することで高速に答えます。

考察

まず、時刻 \(t\) における2人の位置差（高橋君−青木君）を考えます。

• 初期時刻では差は \(-d\)
• 1秒ごとに差は \(B_i-A_i=C_i\) だけ増える

したがって、時刻 \(t\) までの差は [ -d + \sum{s=0}^{t-1} C{(s\bmod N)+1} ] で、追い付く条件は [ \sum{s=0}^{t-1} C{(s\bmod N)+1} \ge d ] です。

つまり「周期列 \(C\) の累積和が \(d\) 以上になる最小の整数時刻」を求めればよいです。

---

素朴に各 2 d クエリで秒ごとにシミュレーションすると、\(d\) が最大 \(10^{15}\) なので不可能です。
また、更新クエリ 1 i a b があるため、事前に全クエリを固定して高速化するのも難しいです。

ここで重要なのは：

• 1周期の累積増加量を \(S=\sum_{i=1}^N C_i\) とする
• 周期内累積和を pref[r] = C_1+\cdots+C_r（pref[0]=0）とする

すると任意の時刻 \(t=kN+r\)（\(0\le r\le N\)）での累積は [ kS + \text{pref}[r] ] と書けます。

場合分け

1. \(S \le 0\) のとき
   周期を重ねても全体として増えない（むしろ減る）ので、最大到達値は最初の1周期内で決まります。
   よって pref[0..N] を見て、\(d\) 以上があればその最小 \(r\) が答え、なければ \(-1\)。

2. \(S > 0\) のとき
   周期を重ねればいずれ増える可能性がある。
   ただし毎周期の中で山谷があるので、周期内最大値 [ M=\max_{0\le r\le N}\text{pref}[r] ] を使う。

   • もし \(d\le M\) なら 0周期目で届く可能性がある
   • もし \(d>M\) なら、少なくとも [ k=\left\lceil\frac{d-M}{S}\right\rceil ] 周期進めれば、その周期内のどこかで届く

この \(k\) を決めた後、base = kS として最小の \(r\)（base + pref[r] >= d）を探せば、答えは [ t=kN+r ] です。

---

更新クエリについては、1点変更後に pref の後ろを作り直せばよいです（rebuild_from(i)）。
制約に \(NQ \le 10^7\) があるため、更新ごと \(O(N)\)・質問ごと \(O(N)\) の実装でも十分間に合います。

アルゴリズム

• 配列
  • \(C_i = B_i-A_i\)
  • pref[0]=0, pref[i]=pref[i-1]+C_i

1 i a b

1. A[i]=a, B[i]=b
2. C[i]=B[i]-A[i]
3. pref[i..N] を再計算

2 d

1. S = pref[N]
2. S <= 0 なら
   • r=0..N で最小の pref[r] >= d を探す
   • あれば r、なければ -1
3. S > 0 なら
   • M = max(pref[0..N])
   • d > M なら k = ceil((d-M)/S)、そうでなければ k=0
   • base = k*S
   • 最小の r で base + pref[r] >= d を探す
   • 答えは k*N + r

計算量

• 時間計算量:
  
  • 更新クエリ 1: \(O(N)\)（pref の後ろ再構築）
    
  • 質問クエリ 2: \(O(N)\)（pref の走査）
    
  • 全体では制約より実質 \(O(NQ)\)（ただし \(NQ \le 10^7\)）
• 空間計算量: \(O(N)\)

実装のポイント

• d が大きいので long long を使う（int は不可）。

• pref[0]=0 を含めて走査すること。r=0 は「時刻0で既に条件を満たすか」を表す重要なケース。

• 切り上げ除算 [ \left\lceil\frac{x}{S}\right\rceil = \frac{x+S-1}{S} ] は x>0 のとき (x + S - 1) / S で実装できる。
  

• S<=0 のときは「1周期内だけ見れば十分」という性質を見落とさないこと。

  ソースコード

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

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

    int N, Q;
    cin >> N >> Q;

    vector<long long> A(N + 1), B(N + 1), C(N + 1), pref(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        cin >> A[i] >> B[i];
        C[i] = B[i] - A[i];
        pref[i] = pref[i - 1] + C[i];
    }

    auto rebuild_from = [&](int i) {
        for (int k = i; k <= N; k++) pref[k] = pref[k - 1] + C[k];
    };

    while (Q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int i;
            long long a, b;
            cin >> i >> a >> b;
            A[i] = a;
            B[i] = b;
            C[i] = B[i] - A[i];
            rebuild_from(i);
        } else {
            long long d;
            cin >> d;

            long long S = pref[N]; // gain per full cycle

            if (S <= 0) {
                bool ok = false;
                long long ans = -1;
                for (int r = 0; r <= N; r++) {
                    if (pref[r] >= d) {
                        ans = r;
                        ok = true;
                        break;
                    }
                }
                if (!ok) cout << -1 << '\n';
                else cout << ans << '\n';
                continue;
            }

            long long M = 0;
            for (int r = 0; r <= N; r++) M = max(M, pref[r]);

            long long k = 0;
            if (d > M) {
                k = (d - M + S - 1) / S;
            }

            long long base = k * S;
            int r_ans = -1;
            for (int r = 0; r <= N; r++) {
                if (base + pref[r] >= d) {
                    r_ans = r;
                    break;
                }
            }

            long long ans = (long long)k * N + r_ans;
            cout << ans << '\n';
        }
    }

    return 0;
}

---

この解説は gpt-5.3-codex によって生成されました。