提出 #76599075

---

ソースコード 拡げる

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

#define ll long long

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

    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;

    string t = s + s;

    int m = 2 * n;

    vector<vector<unsigned short>> lcp(m + 1, vector<unsigned short>(m + 1, 0));

    for (int i = m - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (t[i] == t[j]) {
                lcp[i][j] = min(n, 1 + (int)lcp[i + 1][j + 1]);
            }
        }
    }

    vector<vector<ll>> ans(n, vector<ll>(n + 1, 0));

    for (int p = 0; p < n; p++) {
        vector<ll> add(n + 2, 0), sub(n + 2, 0);

        for (int x = 0; x < n; x++) {
            int same = lcp[x][p];

            if (same == n) {
                continue;
            }

            if (t[x + same] < t[p + same]) {
                add[same + 1]++;
                sub[same + 1] -= same;
            }
        }

        ll cnt = 0;
        ll minus = 0;

        for (int len = 1; len <= n; len++) {
            cnt += add[len];
            minus += sub[len];

            ans[p][len] = cnt * len + minus;
        }
    }

    int pos = 0;

    while (q--) {
        int a, l;
        cin >> a >> l;

        pos = (pos + a) % n;

        cout << ans[pos][l] << '\n';
    }

    return 0;
}

提出情報

ジャッジ結果