Overview

Given \(N\) stones arranged in a circular ring, each engraved with a character, and a current stone position \(P\), the problem asks us to count the number of pairs \((x, \ell)\) of “starting position \(x\) and length \(\ell\)” such that the string \(C(x, \ell)\) is lexicographically smaller than \(C(P, \ell)\).

Analysis

1. Conditions for Lexicographic Comparison

When comparing two strings \(C(x, \ell)\) and \(C(P, \ell)\), the following holds: - Let \(k\) be the length of the longest common prefix (LCP) of \(C(x, N)\) and \(C(P, N)\). - When \(\ell \leq k\): \(C(x, \ell) = C(P, \ell)\). - When \(\ell > k\): The lexicographic ordering of \(C(x, \ell)\) and \(C(P, \ell)\) is determined by the comparison of the \((k+1)\)-th characters, i.e., the characters engraved on stone \((x+k)\) and stone \((P+k)\).

Therefore, \(C(x, \ell) < C(P, \ell)\) holds if and only if all of the following conditions are satisfied: 1. \(k < \ell\) 2. \(S_{x+k} < S_{P+k}\) (where indices account for the circular arrangement)

2. Speeding Up the Counting

If we naively check all \(1 \leq x \leq N\) and \(1 \leq \ell \leq L_i\) for each query, it costs \(O(N^2)\) per query and \(O(QN^2)\) overall, which is too slow. Instead, for each starting position \(x\), we consider the number of valid \(\ell\) values that satisfy the conditions.

Let \(k\) be the LCP when starting from stone \(x\) and stone \(P\). If \(S_{x+k} < S_{P+k}\), then \(C(x, \ell) < C(P, \ell)\) holds for \(\ell = k+1, k+2, \dots, L_i\). The number of such \(\ell\) values is \(\max(0, L_i - k)\).

Therefore, for the current position \(P\) and the upper bound on length \(L\), the answer is: $\(\sum_{x=1}^{N} [S_{x+k} < S_{P+k} \text{ and } k < L] \times (L - k)\)\( where \)k = \text{LCP}(x, P)$.

Algorithm

1. Precomputation (LCP and Frequency Distribution)

First, we compute the LCP for all pairs of stones \((i, j)\). This can be done in \(O(N^2)\) by using DP on the string \(S\) concatenated with itself. Next, we define and aggregate Less[P][k] as “the number of positions \(x\) such that \(\text{LCP}(x, P) = k\) and \(S_{x+k} < S_{P+k}\)”.

2. Answering Queries with Prefix Sums

The answer for a query \((P, L)\) can be transformed as follows: $\(\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)\)$

Both summation parts can be precomputed as prefix sums over \(k\) for each \(P\), allowing each query to be answered in \(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\)

The answer is \(L \times C1[P][L] - C2[P][L]\).

Complexity

• Time Complexity: \(O(N^2 + Q)\)
  • Computing the LCP and precomputing the prefix sums takes \(O(N^2)\).
  • Each query can be answered in \(O(1)\), so the total for all queries is \(O(Q)\).
• Space Complexity: \(O(N^2)\)
  • The Less array and prefix sum arrays use \(O(N^2)\) memory. For \(N=3000\), this amounts to on the order of tens of millions of elements, which fits within the memory limit.

Implementation Notes

• Handling the circular arrangement: By treating the string \(S\) as \(S+S\), circular substrings can be processed as linear substrings.

• Memory optimization: Storing the full LCP DP table requires \(O(N^2)\) space, but since only the previous row is needed, memory can be saved by keeping only one row at a time (however, since the prefix sum arrays already require \(O(N^2)\), this optimization is only worth considering when constraints are tight).

• Fast I/O: Since \(Q\) can be large, in C++ it is recommended to use ios_base::sync_with_stdio(false); cin.tie(NULL); to speed up input and output.

  Source Code

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

---

This editorial was generated by gemini-3-flash-thinking.