Overview

By looking at the “per-second speed difference” \(C_i = B_i - A_i\), the catching-up condition becomes a problem of finding the minimum time at which the cumulative sum reaches at least the initial distance \(d\).
We first calculate “how many full periods are needed to reach it” using periodicity, then linearly search within the final period to efficiently find the answer.

Analysis

First, consider the position difference (Takahashi − Aoki) at time \(t\).

• At the initial time, the difference is \(-d\)
• Each second, the difference increases by \(B_i - A_i = C_i\)

Therefore, the difference up to time \(t\) is [ -d + \sum{s=0}^{t-1} C{(s\bmod N)+1} ] and the catching-up condition is [ \sum{s=0}^{t-1} C{(s\bmod N)+1} \ge d ]

In other words, we need to find the minimum integer time at which the cumulative sum of the periodic sequence \(C\) becomes at least \(d\).

---

Naively simulating second by second for each 2 d query is impossible since \(d\) can be up to \(10^{15}\).
Also, since there are update queries 1 i a b, it is difficult to precompute and speed things up with all queries fixed in advance.

The key observations are:

• Let \(S = \sum_{i=1}^N C_i\) be the total cumulative increase over one period
• Let the prefix sums within a period be pref[r] = C_1 + \cdots + C_r (pref[0] = 0)

Then the cumulative sum at any time \(t = kN + r\) (\(0 \le r \le N\)) can be written as [ kS + \text{pref}[r] ]

Case Analysis

1. When \(S \le 0\):
   Repeating periods does not increase the total (it may even decrease), so the maximum reachable value is determined within the first period.
   Therefore, check pref[0..N]: if any value is at least \(d\), the minimum such \(r\) is the answer; otherwise, output \(-1\).

2. When \(S > 0\):
   Repeating periods will eventually allow the sum to grow.
   However, there are peaks and valleys within each period, so we use the maximum value within a period: [ M = \max_{0 \le r \le N} \text{pref}[r] ]

   • If \(d \le M\), it may be reachable within period 0
   • If \(d > M\), we need to advance at least [ k = \left\lceil\frac{d - M}{S}\right\rceil ] periods before it becomes reachable somewhere within that period

After determining this \(k\), set base = kS and find the minimum \(r\) such that base + pref[r] >= d. The answer is then [ t = kN + r ]

---

For update queries, after a single-point change, we just need to rebuild pref from that point onward (rebuild_from(i)).
Since the constraint guarantees \(NQ \le 10^7\), an implementation with \(O(N)\) per update and \(O(N)\) per query is fast enough.

Algorithm

• Arrays:
  • \(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. Recompute pref[i..N]

2 d

1. S = pref[N]
2. If S <= 0:
   • Find the minimum r in r = 0..N such that pref[r] >= d
   • If found, output r; otherwise, output -1
3. If S > 0:
   • M = max(pref[0..N])
   • If d > M, then k = ceil((d - M) / S); otherwise k = 0
   • base = k * S
   • Find the minimum r such that base + pref[r] >= d
   • The answer is k * N + r

Complexity

• Time complexity:
  • Update query 1: \(O(N)\) (rebuilding the suffix of pref)
  • Question query 2: \(O(N)\) (scanning pref)
  • Overall, effectively \(O(NQ)\) due to constraints (with \(NQ \le 10^7\))
• Space complexity: \(O(N)\)

Implementation Notes

• Since \(d\) can be large, use long long (int is insufficient).

• Make sure to include pref[0] = 0 in the scan. The case r = 0 represents the important case of “the condition is already satisfied at time 0.”

• Ceiling division [ \left\lceil\frac{x}{S}\right\rceil = \frac{x + S - 1}{S} ] can be implemented as (x + S - 1) / S when x > 0.

• Do not overlook the property that when \(S \le 0\), “it suffices to only look within a single period.”

  Source Code

#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;
}

---

This editorial was generated by gpt-5.3-codex.