Overview

This problem asks you to find the minimum integer time at which Takahashi catches up to Aoki, given their periodically changing speeds. Since speeds are updated by queries, efficient recalculation and catch-up determination are required.

Analysis

1. Focus on Relative Speed

Takahashi starts at coordinate \(0\) and Aoki starts at coordinate \(d\). The condition for Takahashi to catch up to Aoki at time \(t\) is: “total distance Takahashi has traveled by time \(t\)” \(\ge\) “total distance Aoki has traveled by time \(t\) \(+ d\)”.

Rearranging this, if we define the difference in speed (relative speed) between Takahashi and Aoki at each second as \(D_i = B_i - A_i\), the problem reduces to finding the smallest non-negative integer \(t\) satisfying: $\(\sum_{s=1}^{t} D_{(s-1 \bmod N) + 1} \ge d\)$

2. Exploit Periodicity

Let \(q\) be the quotient and \(r\) be the remainder when dividing time \(t\) by \(N\) (\(t = qN + r\), where \(1 \le r \le N\)). Let \(S_N = \sum_{i=1}^N D_i\) be the distance closed in one period (\(N\) seconds), and \(S_r = \sum_{i=1}^r D_i\) be the distance closed up to \(r\) seconds within a period. Then the total distance closed by time \(t\) can be expressed as \(q \cdot S_N + S_r\).

3. Determining the Catch-up Condition

For a given \(d\) in query 2, we consider the following two cases:

• When \(S_N \le 0\) (the distance does not shrink, or increases, over one period) In this case, the situation worsens or stays the same with each passing period, so if Takahashi cannot catch up within the first period (\(t=1\) to \(N\)), he can never catch up.

• When \(S_N > 0\) (the distance steadily shrinks each period) In this case, Takahashi will always eventually catch up. For each \(r \in \{1, \dots, N\}\), we find the smallest non-negative integer \(q\) satisfying: \(q \cdot S_N + S_r \ge d \iff q \cdot S_N \ge d - S_r\)

  • If \(d - S_r \le 0\), then \(q = 0\)
  • If \(d - S_r > 0\), then \(q = \lceil (d - S_r) / S_N \rceil\) The minimum \(t = qN + r\) among all such values is the answer.

Algorithm

1. Initialization:
   • Compute the relative speed for each second: \(D_i = B_i - A_i\).
   • Precompute the prefix sums \(S_r = \sum_{i=1}^r D_i\).
2. Query 1 (Update):
   • Update the specified \(i\)-th \(A_i, B_i\) and recompute \(D_i\).
   • Recompute prefix sums \(S_k\) for \(k = i\) to \(N\). This takes \(O(N)\).
3. Query 2 (Calculation):
   • If \(S_N \le 0\), search for the smallest \(r \in \{1, \dots, N\}\) such that \(S_r \ge d\). If none exists, output \(-1\).
   • If \(S_N > 0\), compute the required number of periods \(q\) for each \(r \in \{1, \dots, N\}\), and find the minimum \(t = qN + r\). This takes \(O(N)\).

Complexity

• Time Complexity: \(O(NQ)\)
  • Updating the prefix sums takes \(O(N)\), and determining the catch-up time takes \(O(N)\).
  • Given the constraint \(NQ \le 10^7\), this complexity is sufficient.
• Space Complexity: \(O(N)\)
  • The array sizes for storing speeds and prefix sums depend on \(N\).

Implementation Notes

• Beware of overflow: Since \(d\) can be up to \(10^{15}\) and travel distances can become very large, use 64-bit integer types (long long in C++) for calculations.

• Ceiling division: The computation \(q = \lceil (d - S_r) / S_N \rceil\) can be written using integer division as (d - S_r + S_N - 1) / S_N.

• Fast I/O: Since the number of queries can be large, it is safe to speed up I/O with cin.tie(NULL); ios_base::sync_with_stdio(false); or similar.

  Source Code

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

This editorial was generated by gemini-3-flash-thinking.