Code: A Trivial String Problem

$O(N^4 \cdot Q)$ ↕

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

int compute_for_string(string &str) {
    int n = str.size();

    vector<int> dp(n, 1);
    // dp[i] = Maximum number of pieces to build str[0...i]

    for (int i = 1; i < n; i++) {
        // Try all starting positions of the last piece.
        // str[0...L - 1] + str[L...i]
        for (int L = 1; L <= i; L++) {
            if (str.substr(L, i - L + 1) == str.substr(0, i - L + 1)) {
                dp[i] = max(dp[i], dp[L - 1] + 1);
            }
        }
    }

    return dp[n - 1];
}

void solve() {
    int n, q;
    cin >> n >> q;
    string str;
    cin >> str;

    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        string substr = str.substr(l, r - l + 1);
        long long ans = 0;
        for (int j = l; j <= r; j++) {
            string substr = str.substr(l, j - l + 1);
            ans += compute_for_string(substr);
        }
        cout << ans << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

$O(N^3 \cdot Q)$ ↕

#include <atcoder/string>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

int compute_for_string(string &str) {
    int n = str.size();

    vector<int> z = z_algorithm(str);

    vector<int> dp(n, 1);
    // dp[i] = Maximum number of pieces to build str[0...i]

    for (int i = 1; i < n; i++) {
        // Try all starting positions of the last piece.
        // str[0...L - 1] + str[L...i]
        for (int L = 1; L <= i; L++) {
            if (z[L] >= i - L + 1) {
                dp[i] = max(dp[i], dp[L - 1] + 1);
            }
        }
    }

    return dp[n - 1];
}

void solve() {
    int n, q;
    cin >> n >> q;
    string str;
    cin >> str;

    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        string substr = str.substr(l, r - l + 1);
        long long ans = 0;
        for (int j = l; j <= r; j++) {
            string substr = str.substr(l, j - l + 1);
            ans += compute_for_string(substr);
        }
        cout << ans << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

$O(N^2 \cdot Q)$ ↕

#include <atcoder/string>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

vector<int> compute_for_string(string &str) {
    int n = str.size();

    vector<int> z = z_algorithm(str);

    vector<int> dp(n, 1);
    // dp[i] = Maximum number of pieces to build str[0...i]

    for (int i = 1; i < n; i++) {
        // Try all starting positions of the last piece.
        // str[0...L - 1] + str[L...i]
        for (int L = 1; L <= i; L++) {
            if (z[L] >= i - L + 1) {
                dp[i] = max(dp[i], dp[L - 1] + 1);
            }
        }
    }

    return dp;
}

void solve() {
    int n, q;
    cin >> n >> q;
    string str;
    cin >> str;

    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        long long ans = 0;

        string substr = str.substr(l, r - l + 1);
        vector<int> dp = compute_for_string(substr);
        for (int i = 0; i < (int)dp.size(); i++) {
            ans += dp[i];
        }

        cout << ans << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

$O(N^2 \cdot Q)$ Distributing DP ↕

#include <atcoder/string>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

vector<int> compute_for_string(string &str) {
    int n = str.size();

    vector<int> z = z_algorithm(str);

    vector<int> dp(n, 1);
    // dp[i] = Maximum number of pieces to build str[0...i]

    // Distribute contribution via prefixes.
    for (int i = 1; i < n; i++) {
        int len = z[i];
        for (int j = i; j < i + len; j++) {
            dp[j] = max(dp[j], dp[i - 1] + 1);
        }
    }

    return dp;
}

void solve() {
    int n, q;
    cin >> n >> q;
    string str;
    cin >> str;

    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        long long ans = 0;

        string substr = str.substr(l, r - l + 1);
        vector<int> dp = compute_for_string(substr);
        for (int i = 0; i < (int)dp.size(); i++) {
            ans += dp[i];
        }

        cout << ans << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

$O(N \cdot Log(N) \cdot Q)$ Lazy Segtree (chmax DP) ↕

#include <atcoder/lazysegtree>
#include <atcoder/string>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using S = int;
using F = int;

S op(S a, S b) { return max(a, b); }
S e() { return 0; }
S mapping(F f, S x) { return max(f, x); }
F composition(F f, F g) { return max(f, g); }
F id() { return 0; }

vector<int> compute_for_string(string &str) {
    int n = str.length();

    vector<int> z = z_algorithm(str);
    vector<int> dp(n, 1);

    lazy_segtree<S, op, e, F, mapping, composition, id> seg(n);

    // dp[0] = 1 already.
    for (int i = 1; i < n; i++) {
        int len = z[i];

        int L = i;
        // Atcoder's segtree has [close, open) range.
        int R = min(n, i + len);
        seg.apply(L, R, dp[i - 1] + 1);

        // Collect all range updates affecting position i, including self-update
        // from i.
        dp[i] = max(dp[i], seg.get(i));
    }

    return dp;
}

void solve() {
    int n, q;
    cin >> n >> q;
    string str;
    cin >> str;

    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        long long ans = 0;

        string substr = str.substr(l, r - l + 1);
        vector<int> dp = compute_for_string(substr);
        for (int i = 0; i < (int)dp.size(); i++) {
            ans += dp[i];
        }

        cout << ans << "\n";
    }
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

$O(N \cdot Log(N) \cdot Q)$ Heap Sweep ↕

#include <atcoder/string>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

vector<int> compute_for_string(string &str) {
    int n = str.size();

    vector<int> z = z_algorithm(str);

    vector<int> dp(n, 1);
    // dp[i] = Maximum number of pieces to build str[0...i]

    // will_contribute_till[i] stores all ther intervals with left end at i,
    // along with their contribution.
    vector<vector<pair<int, int>>> will_contribute_till(n);
    priority_queue<pair<int, int>> heap; // (value, R)

    // Distribute contribution via prefixes.
    for (int i = 1; i < n; i++) {
        int len = z[i];
        int L = i;
        int R = i + len - 1;

        will_contribute_till[L].push_back({dp[i - 1] + 1, R});

        // Ordering is important.
        // First, activate everything, then remove expired intervals, then
        // update dp[i].

        // Activate all intervals that start at i.
        for (auto [val, R] : will_contribute_till[i]) {
            heap.push({val, R});
        }

        // Remove expired intervals.
        while (!heap.empty() && heap.top().second < i) {
            heap.pop();
        }

        if (!heap.empty()) {
            dp[i] = max(dp[i], heap.top().first);
        }
    }

    return dp;
}

void solve() {
    int n, q;
    cin >> n >> q;
    string str;
    cin >> str;

    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        long long ans = 0;

        string substr = str.substr(l, r - l + 1);
        vector<int> dp = compute_for_string(substr);
        for (int i = 0; i < (int)dp.size(); i++) {
            ans += dp[i];
        }

        cout << ans << "\n";
    }
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Model solution : silent_wood ↕

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

using ll = long long;

static vector<int> build_z(const string &t) {
    int n = (int)t.size();
    vector<int> z(n, 0);
    if (n == 0)
        return z;
    z[0] = n;

    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        if (i < r)
            z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && t[z[i]] == t[i + z[i]])
            ++z[i];
        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}

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

    int T;
    cin >> T;
    while (T--) {
        int n, q;
        cin >> n >> q;

        string s;
        cin >> s;

        vector<pair<int, int>> queries(q);
        unordered_map<int, vector<pair<int, int>>> groups;
        groups.reserve(q * 2);

        for (int i = 0; i < q; ++i) {
            int l, r;
            cin >> l >> r;
            queries[i] = {l, r};
            groups[l].push_back({i, r});
        }

        vector<ll> ans(q);

        for (auto &entry : groups) {
            int l = entry.first;
            auto &vec = entry.second;

            int maxR = 0;
            for (auto &it : vec)
                maxR = max(maxR, it.second);

            int m = maxR - l + 1;
            string t = s.substr(l - 1, m);

            vector<int> z = build_z(t);

            vector<int> F(m + 1, 0);
            vector<ll> pref(m + 1, 0);

            vector<pair<int, int>> st;
            st.reserve(m);

            for (int x = 1; x <= m; ++x) {
                int p = x - 1;
                if (p >= 1) {
                    st.push_back({p, p + z[p]});
                }

                while (!st.empty() && st.back().second < x) {
                    st.pop_back();
                }

                int pre = st.empty() ? 0 : st.back().first;
                F[x] = F[pre] + 1;
                pref[x] = pref[x - 1] + F[x];
            }

            for (auto &[idx, r] : vec) {
                int len = r - l + 1;
                ans[idx] = pref[len];
            }
        }

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

    return 0;
}