概要

数直線上で周期的に速さが変わる追いかけっこにおいて、速さの表の更新クエリと、初期距離 \(d\) が与えられたときに追いつく最小時刻を求めるクエリを処理する問題です。

考察

差に注目する

各秒で重要なのは、高橋君と青木君の相対的な距離の変化です。時刻 \(s\) から \(s+1\) の1秒間で距離は \(B_i - A_i\) だけ縮まります（\(i = (s \bmod N) + 1\)）。そこで \(g_i = B_i - A_i\) と定義します。

時刻 \(t\) における累積ゲイン（距離を縮めた合計）が \(d\) 以上になれば追いつきます。

周期性の利用

\(prefix[r] = g_1 + g_2 + \cdots + g_r\)（1周期内の累積ゲイン）、\(G = prefix[N]\)（1周期全体のゲイン）とします。

時刻 \(t = qN + r\)（\(0 \le r < N\)）における累積ゲインは： $\(q \cdot G + prefix[r]\)$

追いつく条件は \(q \cdot G + prefix[r] \ge d\) です。

場合分け

\(G \le 0\) の場合： 周期を重ねても距離が縮まらない（むしろ広がる）ので、追いつけるとしたら最初の1周期内（\(q = 0\)）のみです。\(prefix[r] \ge d\) となる最小の \(r\)（\(1 \le r \le N-1\)）を探します。

\(G > 0\) の場合： 各余り \(r \in \{0, 1, \ldots, N-1\}\) について、条件を満たす最小の \(q\) を求めます： - \(prefix[r] \ge d\) なら \(q = 0\)（時刻 \(r\) で追いつく） - そうでなければ \(q = \lceil (d - prefix[r]) / G \rceil\)（時刻 \(qN + r\) で追いつく）

全ての \(r\) について計算し、最小の時刻を答えとします。

アルゴリズム

1. 初期化：\(g_i = B_i - A_i\) を計算し、累積和 \(prefix\) を構築する。
2. クエリ処理：
   • 更新クエリ（型1）：\(g_i\) を更新し、累積和を再構築する（\(O(N)\)）。
   • 問い合わせクエリ（型2）：
     • \(G = prefix[N]\) を確認。
     • \(G \le 0\)：\(prefix[1], prefix[2], \ldots, prefix[N-1]\) を順に見て、\(d\) 以上になる最初の時刻を返す。なければ \(-1\)。
     • \(G > 0\)：各 \(r = 0, 1, \ldots, N-1\) について最小時刻を計算し、全体の最小値を返す。

計算量

• 時間計算量: \(O(NQ)\)（各クエリで \(O(N)\) の処理、\(NQ \le 10^7\) の制約あり）
• 空間計算量: \(O(N)\)

実装のポイント

• \(G > 0\) の場合、\(r = 0\) のとき \(prefix[0] = 0\) で \(d \ge 1\) なので必ず \(q \ge 1\) となり、時刻 \(qN\) が候補になります。これも忘れずに考慮する必要があります。

• 天井除算 \(\lceil (d - prefix[r]) / G \rceil\) はC++では (need + G - 1) / G で計算できます（\(need > 0\) かつ \(G > 0\) のとき）。

• 答えが非常に大きくなり得るため、long long を使用します（最大で約 \(10^{15} \cdot N\) 程度）。

• \(G \le 0\) の場合に \(prefix[N]\)（\(= G\)）自体は候補に含めません。\(G \le 0 < d\) なので \(prefix[N] \ge d\) にはならないためです（ただし途中の \(prefix[r]\) が \(d\) 以上になる可能性はあります）。

  ソースコード

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

---

この解説は claude4.6opus-thinking によって生成されました。