概要

円環上の各開始位置から読める長さ \(\ell\) の文字列を辞書順に並べたとき、各位置の「自分より小さい文字列の個数」を長さごとに求めます。
各クエリは「長さ \(1\) から \(L_i\) まで」の合計なので、長さを \(1\) から順に処理しながら累積して答えます。

考察

クエリで求めたい値は、現在位置を \(P\) とすると

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

です。

そこで、固定した長さ \(\ell\) について

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

と定義すると、クエリの答えは

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

になります。

素朴に各クエリごとにすべての \(x,\ell\) を調べて文字列比較すると、非常に重くなります。
\(Q\) は最大 \(10^5\) なので、クエリごとに \(O(NL)\) やそれ以上かける方法では間に合いません。

一方で \(N \leq 3000\) なので、すべての長さ \(\ell=1,\dots,N\) について、全開始位置 \(x\) の情報を \(O(N^2)\) 程度で前計算できれば十分です。

重要な気づきは、長さ \(\ell\) の文字列は

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

と表せることです。

つまり、長さ \(\ell\) の文字列同士の辞書順は、

1. 先頭文字 \(S_x\)
2. 残り \(\ell-1\) 文字の辞書順ランク

の組で決まります。

長さ \(\ell-1\) の文字列の辞書順ランクが分かっていれば、長さ \(\ell\) のランクも効率よく求められます。

アルゴリズム

まず、長さごとに以下を求めます。

• \(R_\ell[x]\)：文字列 \(C(x,\ell)\) の辞書順ランク
• sumLess[x]：これまで処理した長さについての合計

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

を持つ配列

初期状態として、長さ \(0\) の空文字列はすべて同じなので、

\[ R_0[x] = 0 \]

とします。

長さ \(\ell\) を \(1\) から \(N\) まで順に処理します。

1. 長さ \(\ell\) の文字列をソートする

長さ \(\ell\) の文字列 \(C(x,\ell)\) は、次の組で表せます。

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

この組を辞書順にソートすれば、\(C(x,\ell)\) の辞書順に並んだことになります。

コードでは、文字は \(26\) 種類、ランクは最大でも \(N\) 種類なので、Counting Sort を使って \(O(N)\) で並べています。

2. 同じ文字列ごとにグループ化する

ソート後の順番を見て、同じ組

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

を持つものを同じグループにします。

ソート済み配列で、あるグループが位置 \(i\) から始まるとします。
このとき、そのグループに属する任意の \(x\) について、

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

です。

なぜなら、ソート済み配列でそのグループより前にある \(i\) 個の開始位置は、すべて \(C(x,\ell)\) より辞書順で小さいからです。
同じグループ内の文字列は等しいので、厳密に小さいものには数えません。

例えば、長さ \(1\) で文字列が

a, a, b

のように並ぶ場合、b より小さい開始位置は a が 2 個あるので、答えは 2 です。
単なるランク番号ではなく、「前に何個あるか」を数える必要があります。

そのため、コードではグループの開始位置 i を sumLess[x] に足しています。

3. クエリに答える

クエリは長さ上限 \(L_i\) ごとにまとめておきます。

長さ \(\ell\) の処理が終わった時点で、sumLess[x] には

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

が入っています。

したがって、\(L_i=\ell\) のクエリに対しては、現在位置を \(P\) として

ans[i] = sumLess[P]

で答えられます。

現在位置 \(P\) はクエリを読み込む時点で順にシミュレーションしておきます。
答え自体は後でまとめて計算するため、クエリ番号も一緒に保存しておきます。

計算量

• 時間計算量: \(O(N^2 + Q)\)
• 空間計算量: \(O(N + Q)\)

各長さ \(\ell\) について、全開始位置 \(N\) 個を Counting Sort とグループ化で \(O(N)\) で処理します。
これを \(N\) 回行うので \(O(N^2)\) です。
クエリの読み込み・出力は \(O(Q)\) です。

実装のポイント

• 実装では位置を \(0\)-indexed にしているため、移動は

  p = (p + A) % N;

で処理できます。

• prevRank[x] が \(R_{\ell-1}[x]\)、curRank[x] が \(R_\ell[x]\) に対応します。

• 円環なので、次の位置は

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

としておきます。

• 同じ文字列は同じグループとして扱い、答えに足す値は「ランク番号」ではなく「ソート済み配列でのグループ開始位置」です。

• 答えは最大でも \(O(N^2)\) 程度ですが、安全のため long long を使っています。

  ソースコード

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

---

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