Overview

This problem involves processing queries for a chase on a number line where speeds change periodically: update queries that modify the speed table, and queries that determine the minimum time to catch up given an initial distance \(d\).

Analysis

Focus on the Difference

What matters each second is the relative change in distance between Takahashi and Aoki. During the one second from time \(s\) to \(s+1\), the distance decreases by \(B_i - A_i\) (where \(i = (s \bmod N) + 1\)). We define \(g_i = B_i - A_i\).

Takahashi catches up when the cumulative gain (total distance closed) at time \(t\) becomes at least \(d\).

Utilizing Periodicity

Let \(prefix[r] = g_1 + g_2 + \cdots + g_r\) (cumulative gain within one period), and \(G = prefix[N]\) (gain over one full period).

The cumulative gain at time \(t = qN + r\) (\(0 \le r < N\)) is: $\(q \cdot G + prefix[r]\)$

The catch-up condition is \(q \cdot G + prefix[r] \ge d\).

Case Analysis

When \(G \le 0\): The distance does not decrease (or even increases) over each full period, so catching up is only possible within the first period (\(q = 0\)). We search for the smallest \(r\) (\(1 \le r \le N-1\)) such that \(prefix[r] \ge d\).

When \(G > 0\): For each remainder \(r \in \{0, 1, \ldots, N-1\}\), we find the minimum \(q\) satisfying the condition: - If \(prefix[r] \ge d\), then \(q = 0\) (catches up at time \(r\)) - Otherwise, \(q = \lceil (d - prefix[r]) / G \rceil\) (catches up at time \(qN + r\))

We compute this for all \(r\) and return the minimum time.

Algorithm

1. Initialization: Compute \(g_i = B_i - A_i\) and build the prefix sum array \(prefix\).
2. Query processing:
   • Update query (type 1): Update \(g_i\) and rebuild the prefix sum (\(O(N)\)).
   • Answer query (type 2):
     • Check \(G = prefix[N]\).
     • \(G \le 0\): Scan \(prefix[1], prefix[2], \ldots, prefix[N-1]\) in order and return the first time where the value is at least \(d\). If none exists, return \(-1\).
     • \(G > 0\): For each \(r = 0, 1, \ldots, N-1\), compute the minimum time, and return the overall minimum.

Complexity

• Time complexity: \(O(NQ)\) (\(O(N)\) processing per query, with the constraint \(NQ \le 10^7\))
• Space complexity: \(O(N)\)

Implementation Notes

• When \(G > 0\) and \(r = 0\), we have \(prefix[0] = 0\) and \(d \ge 1\), so \(q \ge 1\) always holds, making time \(qN\) a candidate. This must not be overlooked.

• The ceiling division \(\lceil (d - prefix[r]) / G \rceil\) can be computed in C++ as (need + G - 1) / G (when \(need > 0\) and \(G > 0\)).

• Since answers can be very large, use long long (up to approximately \(10^{15} \cdot N\)).

• When \(G \le 0\), \(prefix[N]\) (\(= G\)) itself is not a candidate. Since \(G \le 0 < d\), \(prefix[N] \ge d\) cannot hold (though intermediate \(prefix[r]\) values may still reach \(d\) or above).

  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> g(N+1);
    vector<long long> prefix(N+1, 0);
    
    for(int i = 1; i <= N; i++){
        long long a, b;
        cin >> a >> b;
        g[i] = b - a;
    }
    
    auto rebuild = [&](){
        prefix[0] = 0;
        for(int i = 1; i <= N; i++){
            prefix[i] = prefix[i-1] + g[i];
        }
    };
    
    rebuild();
    
    while(Q--){
        int type;
        cin >> type;
        if(type == 1){
            int i;
            long long a, b;
            cin >> i >> a >> b;
            g[i] = b - a;
            rebuild();
        } else {
            long long d;
            cin >> d;
            long long G = prefix[N];
            
            if(G <= 0){
                long long ans = -1;
                for(int r = 1; r < N; r++){
                    if(prefix[r] >= d){
                        ans = r;
                        break;
                    }
                }
                cout << ans << '\n';
            } else {
                long long ans = LLONG_MAX;
                for(int r = 0; r < N; r++){
                    long long need = d - prefix[r];
                    long long q;
                    if(need <= 0) q = 0;
                    else q = (need + G - 1) / G;
                    long long t = q * (long long)N + r;
                    if(t < ans) ans = t;
                }
                cout << ans << '\n';
            }
        }
    }
    
    return 0;
}

---

This editorial was generated by claude4.6opus-thinking.