A Trivial String Problem

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 1e18; //❄️
    7const int MM = 1000005;
    8int Z[MM];
    9int cnt[MM];
    10int head[MM];
    11int nxt[MM];
    12int val[MM];
    13int q_head[MM];
    14int q_nxt[105];
    15int q_r[105];
    16int q_id[105];
    17void solve() {
    18    fill(q_head, q_head + MM, -1);
    19    int n, q; cin >> n >> q;
    20    string s; cin >> s;
    21    vector<int> active;
    22    int q_cnt = 0;
    23    for (int i = 0; i < q; i++) {
    24        int l, r;
    25        cin >> l >> r;
    26        if (q_head[l] == -1) {
    27            active.push_back(l);
    28        }
    29        q_r[q_cnt] = r;
    30        q_id[q_cnt] = i;
    31        q_nxt[q_cnt] = q_head[l];
    32        q_head[l] = q_cnt++;
    33    }
    34    vector<ll> ans(q);
    35    for (int l : active) {
    36        vector<pair<int, int>> current_q;
    37        int cur_q = q_head[l];
    38        while (cur_q != -1) {
    39            current_q.push_back({q_r[cur_q], q_id[cur_q]});
    40            cur_q = q_nxt[cur_q];
    41        }
    42        sort(current_q.begin(), current_q.end());
    43        int max_r = current_q.back().first;
    44        int m = max_r - l + 1;
    45        Z[0] = m;
    46        for (int i = 1, L = 0, R = 0; i < m; i++) {
    47            Z[i] = 0;
    48            if (i <= R) Z[i] = min(R - i + 1, Z[i - L]);
    49            while (i + Z[i] < m && s[l - 1 + Z[i]] == s[l - 1 + i + Z[i]]) {
    50                Z[i]++;
    51            }
    52            if (i + Z[i] - 1 > R) {
    53                L = i;
    54                R = i + Z[i] - 1;
    55            }
    56        }
    57        cnt[0] = 1;
    58        int max_val = 0;
    59        ll current_sum = 0;
    60        for (int i = 1; i <= m + 1; i++) head[i] = -1;
    61        int q_indx = 0;
    62        for (int i = 1; i <= m; i++) {
    63            int cur = head[i];
    64            while (cur != -1) {
    65                cnt[val[cur]]--;
    66                cur = nxt[cur];
    67            }
    68            while (max_val > 0 && cnt[max_val] == 0) {
    69                max_val--;
    70            }
    71            int dpi = max_val + 1;
    72            current_sum += dpi;
    73 
    74            while (q_indx < current_q.size() && current_q[q_indx].first - l + 1 == i) {
    75                ans[current_q[q_indx].second] = current_sum;
    76                q_indx++;
    77            }
    78            if (i < m && Z[i] > 0) {
    79                cnt[dpi]++;
    80                if (dpi > max_val) max_val = dpi;
    81                int exp = i + Z[i] + 1;
    82                if (exp <= m) {
    83                    val[i] = dpi;
    84                    nxt[i] = head[exp];
    85                    head[exp] = i;
    86                }
    87            }
    88        }
    89        for (int i = 0; i <= max_val; i++) cnt[i] = 0;
    90        q_head[l] = -1;
    91    }
    92    for (int i = 0; i < q; i++) {
    93        cout << ans[i] << '\n';;
    94    }
    95}
    96int main() {
    97    ios::sync_with_stdio(0); cin.tie(0); 
    98    int t; cin >> t;
    99    while (t--) {
    100        solve();
    101    }
    102    return 0;
    103}