Overview

When we read strings of length \(\ell\) starting from each position on a circular string and sort them lexicographically, we want to compute for each position the “number of strings smaller than it” for each length.
Since each query asks for the total from “length \(1\) to \(L_i\)”, we process lengths from \(1\) in order and accumulate the answers.

Approach

The value we want for a query, given the current position \(P\), is

\[ \sum_{\ell=1}^{L_i} \#\{x \mid C(x,\ell) < C(P,\ell)\} \]

So, for a fixed length \(\ell\), we define

\[ F_\ell(p) = \#\{x \mid C(x,\ell) < C(p,\ell)\} \]

Then the answer to a query is

\[ F_1(P) + F_2(P) + \cdots + F_{L_i}(P) \]

Naively checking all \(x, \ell\) and comparing strings for each query would be extremely slow.
Since \(Q\) can be up to \(10^5\), any approach that takes \(O(NL)\) or more per query will not be fast enough.

On the other hand, since \(N \leq 3000\), it suffices to precompute the information for all starting positions \(x\) across all lengths \(\ell=1,\dots,N\) in about \(O(N^2)\) time.

The key observation is that a string of length \(\ell\) can be expressed as

\[ C(x,\ell) = S_x + C(\mathrm{next}(x), \ell-1) \]

In other words, the lexicographic order between strings of length \(\ell\) is determined by the pair of:

1. The first character \(S_x\)
2. The lexicographic rank of the remaining \(\ell-1\) characters

If we already know the lexicographic ranks for strings of length \(\ell-1\), we can efficiently compute the ranks for length \(\ell\).

Algorithm

For each length, we compute the following:

• \(R_\ell[x]\): the lexicographic rank of string \(C(x,\ell)\)
• sumLess[x]: an array holding the cumulative total over all lengths processed so far

\[ \sum_{k=1}^{\ell} F_k(x) \]

As the initial state, since the empty string of length \(0\) is the same for all positions,

\[ R_0[x] = 0 \]

We process lengths \(\ell\) from \(1\) to \(N\) in order.

1. Sort the strings of length \(\ell\)

A string \(C(x,\ell)\) of length \(\ell\) can be represented by the pair:

\[ (S_x, R_{\ell-1}[\mathrm{next}(x)]) \]

Sorting these pairs lexicographically gives us the lexicographic order of \(C(x,\ell)\).

In the implementation, since there are at most \(26\) distinct characters and at most \(N\) distinct ranks, we use Counting Sort to sort in \(O(N)\).

2. Group identical strings together

After sorting, we group together entries that share the same pair

\[ (S_x, R_{\ell-1}[\mathrm{next}(x)]) \]

Suppose in the sorted array a group starts at position \(i\).
Then, for any \(x\) belonging to that group,

\[ F_\ell(x) = i \]

This is because the \(i\) starting positions before that group in the sorted array all correspond to strings lexicographically smaller than \(C(x,\ell)\).
Strings within the same group are equal, so they are not counted as strictly smaller.

For example, if for length \(1\) the strings are sorted as

a, a, b

then for b, there are 2 starting positions with smaller strings (a appears twice), so the answer is 2.
We need to count “how many come before,” not just a rank number.

Therefore, in the code, we add the group’s starting position i to sumLess[x].

3. Answer the queries

We group queries by their length limit \(L_i\).

After processing length \(\ell\), sumLess[x] contains

\[ \sum_{k=1}^{\ell} F_k(x) \]

Thus, for a query with \(L_i=\ell\), given the current position \(P\):

ans[i] = sumLess[P]

gives the answer.

The current position \(P\) is simulated in order when reading the queries.
Since the actual answers are computed collectively later, we also store the query index alongside.

Complexity

• Time complexity: \(O(N^2 + Q)\)
• Space complexity: \(O(N + Q)\)

For each length \(\ell\), we process all \(N\) starting positions using Counting Sort and grouping in \(O(N)\).
Doing this \(N\) times gives \(O(N^2)\).
Reading and outputting the queries takes \(O(Q)\).

Implementation Notes

• In the implementation, positions are \(0\)-indexed, so movement is handled by

  p = (p + A) % N;

• prevRank[x] corresponds to \(R_{\ell-1}[x]\), and curRank[x] corresponds to \(R_\ell[x]\).

• Since the string is circular, the next position is defined as

  nxt[i] = (i + 1 == N ? 0 : i + 1);

• Identical strings are treated as the same group, and the value added to the answer is not the “rank number” but the “starting position of the group in the sorted array.”

• The answer can be at most around \(O(N^2)\), but long long is used to be safe.

  Source Code

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

struct Query {
    int pos;
    int idx;
};

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

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

    string S;
    cin >> S;

    vector<int> ch(N), nxt(N);
    for (int i = 0; i < N; i++) {
        ch[i] = S[i] - 'a';
        nxt[i] = (i + 1 == N ? 0 : i + 1);
    }

    vector<vector<Query>> queries(N + 1);
    int p = 0;

    for (int i = 0; i < Q; i++) {
        int A, L;
        cin >> A >> L;
        p = (p + A) % N;
        queries[L].push_back({p, i});
    }

    vector<long long> ans(Q);
    vector<long long> sumLess(N, 0);

    vector<int> prevRank(N, 0), curRank(N);
    vector<int> tmp(N), order(N);
    vector<int> cnt(N + 1);

    int rankKinds = 1;

    for (int len = 1; len <= N; len++) {
        fill(cnt.begin(), cnt.begin() + rankKinds, 0);

        for (int x = 0; x < N; x++) {
            cnt[prevRank[nxt[x]]]++;
        }

        int acc = 0;
        for (int r = 0; r < rankKinds; r++) {
            int c = cnt[r];
            cnt[r] = acc;
            acc += c;
        }

        for (int x = 0; x < N; x++) {
            int key = prevRank[nxt[x]];
            tmp[cnt[key]++] = x;
        }

        int cntChar[26] = {};
        for (int i = 0; i < N; i++) {
            cntChar[ch[tmp[i]]]++;
        }

        acc = 0;
        for (int c = 0; c < 26; c++) {
            int v = cntChar[c];
            cntChar[c] = acc;
            acc += v;
        }

        for (int i = 0; i < N; i++) {
            int x = tmp[i];
            order[cntChar[ch[x]]++] = x;
        }

        int newRankKinds = 0;

        for (int i = 0; i < N;) {
            int x0 = order[i];
            int c0 = ch[x0];
            int r0 = prevRank[nxt[x0]];

            int j = i + 1;
            while (j < N) {
                int x = order[j];
                if (ch[x] != c0 || prevRank[nxt[x]] != r0) break;
                j++;
            }

            for (int k = i; k < j; k++) {
                int x = order[k];
                curRank[x] = newRankKinds;
                sumLess[x] += i;
            }

            newRankKinds++;
            i = j;
        }

        for (const auto& q : queries[len]) {
            ans[q.idx] = sumLess[q.pos];
        }

        prevRank.swap(curRank);
        rankKinds = newRankKinds;
    }

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.