概要

各質問について、区間 \([L,R]\) のタスクだけを \(G=0, C=0\) から処理したときの、限界到達回数 \(C\) と最終ストレス値 \(G\) を求めます。

ポイントは、\(K \leq 300\) と小さいため、「ある区間を処理すると、入力されたストレス値 \(G\) がどう変化するか」を全状態について前計算できることです。

考察

まず、タスク \(i\) の処理を見直します。

タスク処理では、

1. \(G \leftarrow G + A_i\)
2. \(G \leftarrow \max(0, G - B_i)\)
3. \(G \geq K\) なら \(C\) を \(1\) 増やし、\(G \leftarrow 0\)

を行います。

ステップ 1, 2 をまとめると、

\[ G \leftarrow \max(0, G + A_i - B_i) \]

です。

したがって、タスク \(i\) の影響は \(A_i\) と \(B_i\) を個別に見る必要はなく、

\[ D_i = A_i - B_i \]

だけで決まります。

現在のストレス値を \(g\) とすると、タスク \(i\) 後は次のようになります。

• \(g + D_i \geq K\) なら、限界に達して \(C\) が \(1\) 増え、\(g=0\)
• \(g + D_i \leq 0\) なら、\(g=0\)
• それ以外なら、\(g \leftarrow g + D_i\)

ここで重要なのは、各タスクの処理後、必ず

\[ 0 \leq G < K \]

が成り立つことです。

なぜなら、\(G \geq K\) になった場合はすぐに \(0\) に戻されるからです。

つまり、各区間の処理は、入力 \(G \in \{0,1,\dots,K-1\}\) に対して、

• 限界到達回数がいくつ増えるか
• 最終的な \(G\) がいくつになるか

という「関数」として表せます。

---

素朴に各質問ごとに \(L\) から \(R\) までシミュレーションすると、最悪で

\[ O(NQ) \]

となります。

制約は \(N,Q \leq 6 \times 10^4\) なので、これは間に合いません。

そこで、区間ごとの「変化の関数」を前計算し、質問ではそれらを合成して高速に答えます。

アルゴリズム

1. 各タスクの差分を持つ

各タスクについて、

\[ D_i = A_i - B_i \]

を計算しておきます。

1 個のタスクを適用する処理は次のようになります。

x = g + D_i;
if (x >= K) {
    c++;
    g = 0;
} else if (x <= 0) {
    g = 0;
} else {
    g = x;
}

2. ブロックに分ける

タスク列を長さ \(16\) 程度の小さなブロックに分けます。

各ブロックについて、すべての初期値

\[ g = 0,1,\dots,K-1 \]

に対して、そのブロック全体を処理した結果を前計算します。

具体的には、ブロック \(b\) について、

• nxt[b][g] : 初期ストレス値が \(g\) のとき、ブロック処理後のストレス値
• add[b][g] : 初期ストレス値が \(g\) のとき、ブロック内で増える限界到達回数

を持ちます。

3. ブロック列の上にセグメント木を作る

ブロックを葉とするセグメント木を作ります。

各ノードは、対応する連続したブロック列全体の変換を持ちます。

あるノードが左部分 \(L\) と右部分 \(R\) からなるとします。

初期値を \(g\) とすると、

1. 左部分を処理する
   
   • 限界到達回数が add[L][g] 増える
   • ストレス値が nxt[L][g] になる
2. その結果を入力として右部分を処理する

したがって、合成は次のようになります。

\[ mid = nxt_L[g] \]

\[ add[g] = add_L[g] + add_R[mid] \]

\[ nxt[g] = nxt_R[mid] \]

このようにして、セグメント木の各ノードに対して、全 \(g\) について値を計算します。

4. 質問に答える

質問区間 \([L,R]\) に対して、まず \(L,R\) が属するブロックを見ます。

• 左端ブロックの途中部分
• 右端ブロックの途中部分

は、要素数が高々ブロックサイズなので、直接シミュレーションします。

その間に完全に含まれるブロック列については、セグメント木を使ってまとめて適用します。

注意点として、区間の処理は順番が重要です。

関数の合成は一般に交換できないため、セグメント木で得られたノードを必ず左から右の順に適用する必要があります。

コードでは、右側から出てきたノードを一旦配列に保存し、最後に逆順で適用することで、全体として左から右の順序を保っています。

計算量

ブロックサイズを \(B\) とします。コードでは \(B=16\) です。

• 前計算:

  • 各ブロックについて \(K\) 通りの初期値をシミュレーションするので \(O(NK)\)
  • セグメント木の構築に \(O\left(\frac{N}{B}K\right)\)

• 各質問:

  • 両端の端数部分を直接処理して \(O(B)\)
  • セグメント木のノードをたどって \(O\left(\log \frac{N}{B}\right)\)

したがって全体では、

• 時間計算量: \(O\left(NK + Q\left(B + \log \frac{N}{B}\right)\right)\)
• 空間計算量: \(O\left(\frac{N}{B}K\right)\)

\(B=16\) は定数なので、おおよそ

• 時間計算量: \(O(NK + Q\log N)\)
• 空間計算量: \(O(NK/B)\)

と見なせます。

実装のポイント

• 各タスクは \(A_i-B_i\) だけを使えば十分です。

• 各タスク処理後は必ず \(0 \leq G < K\) になるため、状態数は \(K\) 個だけです。

• nxt には最終的な \(G\)、add には増加する限界到達回数を保存します。

• セグメント木のノードを合成するときは、左を処理した後のストレス値を右の入力にします。

• 区間クエリでは、処理順序を必ず左から右に保つ必要があります。

• \(K \leq 300\)、限界到達回数は最大でも \(N \leq 60000\) なので、コードでは uint16_t に収まります。

  ソースコード

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

static inline void apply_delta(int d, int K, int &g, int &c) {
    int x = g + d;
    if (x >= K) {
        ++c;
        g = 0;
    } else if (x <= 0) {
        g = 0;
    } else {
        g = x;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K, Q;
    cin >> N >> K >> Q;

    vector<int> D(N);
    for (int i = 0; i < N; ++i) {
        int A, B;
        cin >> A >> B;
        D[i] = A - B;
    }

    constexpr int BS = 16;
    int nb = (N + BS - 1) / BS;

    int SZ = 1;
    while (SZ < nb) SZ <<= 1;

    int nodes = 2 * SZ;
    vector<uint16_t> nxt((size_t)nodes * K);
    vector<uint16_t> add((size_t)nodes * K, 0);

    for (int b = 0; b < SZ; ++b) {
        size_t base = (size_t)(SZ + b) * K;
        for (int g = 0; g < K; ++g) {
            nxt[base + g] = (uint16_t)g;
        }
    }

    for (int b = 0; b < nb; ++b) {
        int s = b * BS;
        int e = min(N, s + BS);
        size_t base = (size_t)(SZ + b) * K;

        for (int g0 = 0; g0 < K; ++g0) {
            int g = g0, c = 0;
            for (int i = s; i < e; ++i) {
                apply_delta(D[i], K, g, c);
            }
            nxt[base + g0] = (uint16_t)g;
            add[base + g0] = (uint16_t)c;
        }
    }

    for (int v = SZ - 1; v >= 1; --v) {
        size_t base = (size_t)v * K;
        size_t lb = (size_t)(v << 1) * K;
        size_t rb = (size_t)((v << 1) | 1) * K;

        for (int g0 = 0; g0 < K; ++g0) {
            int mid = nxt[lb + g0];
            add[base + g0] = (uint16_t)(add[lb + g0] + add[rb + mid]);
            nxt[base + g0] = nxt[rb + mid];
        }
    }

    auto apply_node = [&](int v, int &g, int &c) {
        size_t idx = (size_t)v * K + g;
        c += add[idx];
        g = nxt[idx];
    };

    while (Q--) {
        int L, R;
        cin >> L >> R;
        --L;
        --R;

        int g = 0, c = 0;
        int bl = L / BS;
        int br = R / BS;

        if (bl == br) {
            for (int i = L; i <= R; ++i) {
                apply_delta(D[i], K, g, c);
            }
        } else {
            int left_end = min(N, (bl + 1) * BS);
            for (int i = L; i < left_end; ++i) {
                apply_delta(D[i], K, g, c);
            }

            int ql = bl + 1;
            int qr = br;
            if (ql < qr) {
                int l = ql + SZ;
                int r = qr + SZ;
                int rights[64];
                int rc = 0;

                while (l < r) {
                    if (l & 1) apply_node(l++, g, c);
                    if (r & 1) rights[rc++] = --r;
                    l >>= 1;
                    r >>= 1;
                }

                while (rc > 0) {
                    apply_node(rights[--rc], g, c);
                }
            }

            int right_start = br * BS;
            for (int i = right_start; i <= R; ++i) {
                apply_delta(D[i], K, g, c);
            }
        }

        cout << c << ' ' << g << '\n';
    }

    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。