概要

円環状に並んだ \(N\) 個の石に刻まれた文字から作られる文字列について、現在の石の位置 \(P\) を基準として、「開始位置 \(x\) と長さ \(\ell\)」の組 \((x, \ell)\) のうち、文字列 \(C(x, \ell)\) が \(C(P, \ell)\) より辞書順で小さいものの個数を求める問題です。

考察

1. 辞書順比較の条件

2つの文字列 \(C(x, \ell)\) と \(C(P, \ell)\) を比較する際、以下のようになります。 - \(k\) を \(C(x, N)\) と \(C(P, N)\) の最長共通接頭辞（LCP）の長さとします。 - \(\ell \leq k\) のとき：\(C(x, \ell) = C(P, \ell)\) です。 - \(\ell > k\) のとき：\(C(x, \ell)\) と \(C(P, \ell)\) の辞書順の大小関係は、\((k+1)\) 文字目の大小関係、つまり石 \((x+k)\) と石 \((P+k)\) に刻まれた文字の比較で決まります。

したがって、\(C(x, \ell) < C(P, \ell)\) となるのは、以下の条件をすべて満たすときです。 1. \(k < \ell\) 2. \(S_{x+k} < S_{P+k}\) （ここでインデックスは円環を考慮）

2. 数え上げの高速化

各クエリで \(1 \leq x \leq N\) と \(1 \leq \ell \leq L_i\) をすべて調べると \(O(N^2)\) かかり、全体で \(O(QN^2)\) となり間に合いません。 そこで、開始位置 \(x\) ごとに条件を満たす \(\ell\) の個数を考えます。

石 \(x\) と石 \(P\) を開始点としたときの LCP を \(k\) とします。もし \(S_{x+k} < S_{P+k}\) であれば、\(\ell\) が \(k+1, k+2, \dots, L_i\) のときに \(C(x, \ell) < C(P, \ell)\) となります。 この \(\ell\) の個数は、\(\max(0, L_i - k)\) です。

したがって、現在の位置 \(P\) と長さの上限 \(L\) に対して求める答えは以下のようになります。 $\(\sum_{x=1}^{N} [S_{x+k} < S_{P+k} \text{ かつ } k < L] \times (L - k)\)\( ここで \)k = \text{LCP}(x, P)$ です。

アルゴリズム

1. 前計算（LCPと頻度分布）

まず、すべての石のペア \((i, j)\) について LCP を求めます。これは文字列 \(S\) を2つ繋げたものに対して DP を用いることで \(O(N^2)\) で計算可能です。 次に、Less[P][k] を「\(\text{LCP}(x, P) = k\) かつ \(S_{x+k} < S_{P+k}\) となる \(x\) の個数」と定義して集計します。

2. 累積和によるクエリ回答

クエリ \((P, L)\) に対する答えは次のように変形できます。 $\(\sum_{k=0}^{L-1} \text{Less}[P][k] \times (L - k) = L \times \left( \sum_{k=0}^{L-1} \text{Less}[P][k] \right) - \left( \sum_{k=0}^{L-1} \text{Less}[P][k] \times k \right)\)$

この2つの総和部分は、\(P\) ごとに \(k\) に関する累積和を前計算しておくことで、各クエリ \(O(1)\) で計算できます。 - \(C1[P][L] = \sum_{k=0}^{L-1} \text{Less}[P][k]\) - \(C2[P][L] = \sum_{k=0}^{L-1} \text{Less}[P][k] \times k\)

答えは \(L \times C1[P][L] - C2[P][L]\) となります。

計算量

• 時間計算量: \(O(N^2 + Q)\)
  • LCPの計算および累積和の前計算に \(O(N^2)\) かかります。
  • 各クエリには \(O(1)\) で回答できるため、全体で \(O(Q)\) です。
• 空間計算量: \(O(N^2)\)
  • Less 配列や累積和配列に \(O(N^2)\) のメモリを使用します。\(N=3000\) の場合、数千万要素程度なのでメモリ制限内に収まります。

実装のポイント

• 円環の扱い: 文字列 \(S\) を \(S+S\) として扱うことで、円環上の部分文字列を直線上の部分文字列として処理できます。

• メモリ節約: LCP の DP テーブルをそのまま保持すると \(N^2\) の領域が必要ですが、1行前のデータのみを保持するようにすれば節約可能です（ただし、累積和配列等で結局 \(O(N^2)\) 必要になるため、制約が厳しい場合のみ検討します）。

• 高速な入出力: \(Q\) が大きいため、C++ の場合は ios_base::sync_with_stdio(false); cin.tie(NULL); を使用して入出力を高速化することが推奨されます。

  ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;

/**
 * The problem asks us to count pairs (x, l) such that the string C(x, l) is lexicographically
 * smaller than C(P, l), where x is the starting position and l is the length.
 * 
 * Let k = LCP(x, P) be the length of the longest common prefix of the circular strings
 * starting at stones x and P.
 * - If k >= l, then C(x, l) == C(P, l).
 * - If k < l, then C(x, l) < C(P, l) if and only if the character at stone (x + k)
 *   is smaller than the character at stone (P + k).
 * 
 * For a given P and L, we need to calculate:
 *   sum_{x=1 to N} sum_{l=1 to L} [C(x, l) < C(P, l)]
 * 
 * This is equivalent to:
 *   sum_{x: k=LCP(x,P)<N and S[(x+k)%N] < S[(P+k)%N]} (L - k)
 * where the inner term (L - k) comes from counting l in the range [k+1, L].
 * 
 * We can precompute Less[P][k], which is the count of x such that LCP(x, P) == k
 * and S[(x+k)%N] < S[(P+k)%N].
 * Then the answer for a query (P, L) is:
 *   sum_{k=0 to L-1} Less[P][k] * (L - k)
 * This can be computed in O(1) using prefix sums.
 */

// Global arrays are zero-initialized and allocated in the data segment.
static int Less[3000][3000];
static int C1[3000][3001];
static int C2[3000][3001];
static int lcp_a[6000];
static int lcp_b[6000];

int main() {
    // Optimization for fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    string S;
    cin >> S;

    // Concatenate S to handle circularity for lengths up to N
    string S2 = S + S;
    int N2 = 2 * N;

    int* p_curr = lcp_a;
    int* p_next = lcp_b;

    // Precompute Less[P][k] in O(N^2)
    // We use a DP to find the linear LCP of substrings of S2.
    for (int i = N2 - 1; i >= 0; i--) {
        for (int j = N2 - 1; j >= 0; j--) {
            if (S2[i] == S2[j]) {
                if (i == N2 - 1 || j == N2 - 1) p_curr[j] = 1;
                else p_curr[j] = 1 + p_next[j + 1];
            } else {
                p_curr[j] = 0;
            }
            
            // Only consider starting positions within the original string length N
            if (i < N && j < N) {
                int k = p_curr[j];
                // If circular LCP is less than N, check the first differing character
                if (k < N && S2[i + k] < S2[j + k]) {
                    Less[j][k]++;
                }
            }
        }
        // Swap pointers to move to the next row of the DP table
        int* temp = p_curr;
        p_curr = p_next;
        p_next = temp;
    }

    // Precompute prefix sums C1 and C2 for O(1) query response
    // C1[p][l] = sum_{k=0 to l-1} Less[p][k]
    // C2[p][l] = sum_{k=0 to l-1} Less[p][k] * k
    for (int p = 0; p < N; p++) {
        C1[p][0] = 0;
        C2[p][0] = 0;
        for (int l = 1; l <= N; l++) {
            C1[p][l] = C1[p][l - 1] + Less[p][l - 1];
            C2[p][l] = C2[p][l - 1] + Less[p][l - 1] * (l - 1);
        }
    }

    int P = 0; // Current stone position (0-indexed)
    for (int i = 0; i < Q; i++) {
        int A, L;
        cin >> A >> L;
        // Update current position
        P = (P + A) % N;
        // Calculate the answer using the precomputed prefix sums:
        // sum_{k=0 to L-1} Less[P][k] * (L - k) = L * C1[P][L] - C2[P][L]
        long long ans = (long long)L * C1[P][L] - (long long)C2[P][L];
        cout << ans << "\n";
    }

    return 0;
}

---

この解説は gemini-3-flash-thinking によって生成されました。