概要

\(N\) 個のタスクの部分列 \([L, R]\) を処理したときのストレス値と限界回数を \(Q\) 回求める問題です。ストレス値 \(G\) が常に \(0\) 以上 \(K\) 未満に収まることを利用し、平方分割（sqrt decomposition） で高速に処理します。

考察

素朴なアプローチ

各クエリに対してタスクを \(L\) から \(R\) まで1つずつシミュレーションすると、1クエリあたり最悪 \(O(N)\) かかり、全体で \(O(NQ)\) です。\(N, Q \leq 6 \times 10^4\) なので最悪 \(3.6 \times 10^9\) となり TLE です。

重要な気づき：状態空間が小さい

ステップ 3 の処理に注目します。\(G \geq K\) ならリセットされるので、各タスクの処理後のストレス値 \(G\) は必ず \(0\) 以上 \(K-1\) 以下 です。\(K \leq 300\) なので、取りうる状態はたったの \(300\) 通りです。

解決のアイデア

タスク列をサイズ \(\sqrt{N}\) 程度のブロックに分割します。各ブロックについて、「開始時のストレス値が \(g\)（\(0 \leq g < K\)）のとき、ブロック全体を処理した後のストレス値と限界回数はいくつか」 を事前に計算しておけば、ブロック単位で \(O(1)\) の遷移が可能になります。

アルゴリズム

前処理

1. タスク列を \(\sqrt{N}\) 個ずつのブロックに分割する。
2. 各ブロック \(b\) について、開始ストレス値 \(g = 0, 1, \ldots, K-1\) のそれぞれに対し、ブロック内の全タスクを順にシミュレーションし、以下を記録する：
   • block_next[b][g]：処理後のストレス値
   • block_count[b][g]：限界に達した回数

クエリ処理

クエリ \([L, R]\) に対し、区間を3つに分ける：

[L, ... 左端ブロックの末尾] | [完全なブロック群] | [右端ブロックの先頭, ..., R]

1. 左端の半端部分：タスクを1つずつシミュレーション（\(O(\sqrt{N})\)）
2. 中間の完全なブロック群：前処理の結果を使い、ブロックごとに \(O(1)\) で遷移（\(O(\sqrt{N})\) ブロック）
3. 右端の半端部分：タスクを1つずつシミュレーション（\(O(\sqrt{N})\)）

具体例

\(K = 5\), ブロックサイズ 3 で、あるブロックが「\(A = [3, 2, 4],\ B = [1, 0, 3]\)」のとき：

• 開始 \(g=0\)：\(0 \xrightarrow{+3-1} 2 \xrightarrow{+2-0} 4 \xrightarrow{+4-3} 5 \geq 5\) → リセット → 最終 \(g=0\), \(c=1\)
• 開始 \(g=2\)：\(2 \xrightarrow{+3-1} 4 \xrightarrow{+2-0} 6 \geq 5\) → リセット → \(0 \xrightarrow{+4-3} 1\) → 最終 \(g=1\), \(c=1\)

このように全 \(K\) 通りの開始状態を事前計算しておきます。

計算量

• 前処理の時間計算量: \(O(N \times K)\)
  • ブロック数 \(\frac{N}{\sqrt{N}} = \sqrt{N}\) 個、各ブロックで \(K\) 通りの初期値 × ブロックサイズ \(\sqrt{N}\)
  • \(\sqrt{N} \times K \times \sqrt{N} = NK\)
• クエリ処理の時間計算量: \(O(Q \times \sqrt{N})\)
• 全体の時間計算量: \(O(NK + Q\sqrt{N})\)
  • \(N = 6 \times 10^4, K = 300\) のとき \(NK = 1.8 \times 10^7\)、\(Q\sqrt{N} \approx 1.5 \times 10^7\)
• 空間計算量: \(O(\sqrt{N} \times K + N)\)

実装のポイント

• オーバーフロー対策：\(A_i\) が最大 \(10^9\) なので、\(G + A_i\) の計算時に long long を使う必要があります。ただし、ステップ 3 の後は \(G < K \leq 300\) に収まるので、状態としては int で十分です。

• ブロックサイズの選択：sqrt(N) を使い、端数はブロック数の調整で吸収します。

• 同一ブロック内のクエリ：\(L\) と \(R\) が同じブロックに属する場合は、前処理を使わず直接シミュレーションします。

• 0-indexed への変換：入力は 1-indexed なので、L--; R--; で変換しています。

  ソースコード

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, K, Q;
    cin >> N >> K >> Q;
    
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
    
    int block_size = max(1, (int)sqrt(N));
    int num_blocks = (N + block_size - 1) / block_size;
    
    vector<vector<int>> block_next(num_blocks, vector<int>(K));
    vector<vector<int>> block_count(num_blocks, vector<int>(K));
    
    for (int b = 0; b < num_blocks; b++) {
        int start = b * block_size;
        int end = min(N, start + block_size);
        for (int g = 0; g < K; g++) {
            int cur_g = g;
            int cur_c = 0;
            for (int i = start; i < end; i++) {
                long long ng = (long long)cur_g + A[i];
                ng = max(0LL, ng - B[i]);
                if (ng >= K) {
                    cur_c++;
                    cur_g = 0;
                } else {
                    cur_g = (int)ng;
                }
            }
            block_next[b][g] = cur_g;
            block_count[b][g] = cur_c;
        }
    }
    
    for (int q = 0; q < Q; q++) {
        int L, R;
        cin >> L >> R;
        L--; R--;
        
        int cur_g = 0, cur_c = 0;
        
        int lb = L / block_size;
        int rb = R / block_size;
        
        if (lb == rb) {
            for (int i = L; i <= R; i++) {
                long long ng = (long long)cur_g + A[i];
                ng = max(0LL, ng - B[i]);
                if (ng >= K) {
                    cur_c++;
                    cur_g = 0;
                } else {
                    cur_g = (int)ng;
                }
            }
        } else {
            int left_end = (lb + 1) * block_size - 1;
            for (int i = L; i <= left_end; i++) {
                long long ng = (long long)cur_g + A[i];
                ng = max(0LL, ng - B[i]);
                if (ng >= K) {
                    cur_c++;
                    cur_g = 0;
                } else {
                    cur_g = (int)ng;
                }
            }
            for (int b = lb + 1; b < rb; b++) {
                cur_c += block_count[b][cur_g];
                cur_g = block_next[b][cur_g];
            }
            int right_start = rb * block_size;
            for (int i = right_start; i <= R; i++) {
                long long ng = (long long)cur_g + A[i];
                ng = max(0LL, ng - B[i]);
                if (ng >= K) {
                    cur_c++;
                    cur_g = 0;
                } else {
                    cur_g = (int)ng;
                }
            }
        }
        
        cout << cur_c << " " << cur_g << "\n";
    }
    
    return 0;
}

---

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