CLUNQUE.cpp

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;

int n, q;
string s;
vector<pair<pair<int, int>, int>> queries[MAXN];
pair<int, int> ans[MAXN];

struct SegTree {
    int n;
    vector<int> tree;

    SegTree(int n_) {
        n = 1; while (n < n_) n <<= 1;
        tree.resize(n << 1);
        for(int i = 0; i < (n << 1); i++)
            tree[i] = MAXN;
    }

    void update(int i, int v) {
        tree[i + n] = v;
        for(i = (i + n) >> 1; i > 0; i >>= 1)
            tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
    }

    int query(int i, int j) {
        int v = MAXN;
        for (i += n, j += n; i <= j; i = (i + 1) >> 1, j = (j - 1) >> 1){
            if ((i & 1) == 1) v = min(tree[i], v);
            if ((j & 1) == 0) v = min(tree[j], v);
        }
        return v;
    }
};

vector<int> suffix_array(string s) {
    s += "!";
    const int ALPHA = 256, n = (int) s.size();
    vector<int> suf(n), cls(s.begin(), s.end());
    iota(suf.begin(), suf.end(), 0);
    for (int len = 0, num_cls = ALPHA; len < n; len ? len <<= 1 : ++len) {
        vector<int> suf_aux(n), new_cls(n), radix(num_cls);
        for (int i = 0; i < n; ++i) {
            suf_aux[i] = suf[i] - len;
            if (suf_aux[i] < 0) suf_aux[i] += n;
            radix[cls[suf_aux[i]]]++;
        }
        for (int i = 1; i < num_cls; ++i) radix[i] += radix[i - 1];
        for (int i = n - 1; ~i; --i) suf[--radix[cls[suf_aux[i]]]] = suf_aux[i];
        num_cls = 1; new_cls[suf[0]] = 0;
        for (int i = 1; i < n; ++i) {
            if (cls[suf[i]] != cls[suf[i - 1]] || cls[suf[i] + len] != cls[suf[i - 1] + len])
                ++num_cls;
            new_cls[suf[i]] = num_cls - 1;
        }
        cls = std::move(new_cls);
    }
    for (int i = 0; i < n - 1; ++i) suf[i] = suf[i + 1];
    suf.pop_back();
    return suf;
}
vector<int> compute_lcp(const string &s, const vector<int> &suf) {
    const int n = (int) s.size();
    vector<int> rank(n), lcp(n - 1);
    for (int i = 0; i < n; ++i) rank[suf[i]] = i;
    for (int i = 0, k = 0; i < n; ++i, k = max(0, k - 1)) {
        if (rank[i] == n - 1) { k = 0; continue; }
        int j = suf[rank[i] + 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) ++k;
        lcp[rank[i]] = k;
    }
    return lcp;
}

void solve(){
    string aux = s;
    auto suf = suffix_array(aux);
    auto lcp = compute_lcp(aux, suf);
    vector<int> ord(n);
    for (int i = 0; i < n; ++i) {
        ord[suf[i]] = i;
    }
    int sz = lcp.size();
    vector<int> tree(2 * sz);
    for(int i = 0; i < sz; i++)
        tree[sz + i] = lcp[i];
    for(int i = sz - 1; i > 0; i--)
        tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
    auto LCP = [&] (int i, int j) {
        i = ord[i], j = ord[j];
        if (i > j) swap(i, j);
        int res = MAXN;
        for (i += sz, j += sz; i < j; i /= 2, j /= 2) {
            if (i & 1) res = min(res, tree[i++]);
            if (j & 1) res = min(res, tree[--j]);
        }
        return res;
    };
    vector<int> min_length_unique(n, n + 2), nxt_good(n);
    int prev_lcp = 0;
    for(int i = 0; i < n - 1; i++){
        int curr_lcp = LCP(suf[i], suf[i + 1]);
        int mx = max(prev_lcp, curr_lcp);
        if(mx < n - suf[i])
            min_length_unique[suf[i]] = mx + 1;
        prev_lcp = curr_lcp;
    }
    if(max(0, prev_lcp) < n - suf[n - 1])
        min_length_unique[suf[n - 1]] = max(0, prev_lcp) + 1;
    pair<int, int> hola[n];
    for(int i = 0; i < n; i++) {
        nxt_good[i] = i + min_length_unique[i] - 1;
        hola[i] = {nxt_good[i], i};
    }
    sort(hola, hola + n);
    SegTree st(n);
    int id = 0;
    for(int i = 0; i < n; i++){
        while(id < n && hola[id].first <= i){
            st.update(hola[id].second, ord[hola[id].second]);
            id++;
        }
        for(auto x : queries[i]){
            int mn = st.query(x.first.first, i - x.first.second + 1);
            if(mn == MAXN)
                ans[x.second] = {-2, -2};
            else
                ans[x.second] = {suf[mn], max(suf[mn] + x.first.second - 1, nxt_good[suf[mn]])};
        }
    }
    int mx = 0;
    for(int i = 0; i < q; i++)
        cout << ans[i].first + 1 << " " << ans[i].second + 1 << "\n";
    for(int i = 0; i < n; i++)
        queries[i].clear();
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    cin >> t;
    while (t--) {
        cin >> n >> s;
        cin >> q;
        for(int i = 0; i < q; i++){
            int l, r, k;
            cin >> l >> r >> k;
            l--, r--;
            assert(0 <= l && l < n && l <= r && r < n && r - l + 1 >= k);
            queries[r].push_back({{l, k}, i});
        }
        solve();
    }
    return 0;
}