SA + Cartesian tree

ABC280H.cc

#include <bits/stdc++.h>
using int64 = long long;
const int Q = 998244353;

void induced_sort(const std::vector<int> &vec, int val_range,
                  std::vector<int> &SA, const std::vector<bool> &sl,
                  const std::vector<int> &lms_idx) {
  std::vector<int> l(val_range, 0), r(val_range, 0);
  for (int c : vec) {
    if (c + 1 < val_range)
      ++l[c + 1];
    ++r[c];
  }
  std::partial_sum(l.begin(), l.end(), l.begin());
  std::partial_sum(r.begin(), r.end(), r.begin());
  fill(SA.begin(), SA.end(), -1);
  for (int i = lms_idx.size() - 1; i >= 0; --i)
    SA[--r[vec[lms_idx[i]]]] = lms_idx[i];
  for (int i : SA)
    if (i >= 1 && sl[i - 1]) {
      SA[l[vec[i - 1]]++] = i - 1;
    }
  std::fill(r.begin(), r.end(), 0);
  for (int c : vec)
    ++r[c];
  std::partial_sum(r.begin(), r.end(), r.begin());
  for (int k = SA.size() - 1, i = SA[k]; k >= 1; --k, i = SA[k])
    if (i >= 1 && !sl[i - 1]) {
      SA[--r[vec[i - 1]]] = i - 1;
    }
}
std::vector<int> SA_IS(const std::vector<int> &vec, int val_range) {
  const int n = vec.size();
  std::vector<int> SA(n), lms_idx;
  std::vector<bool> sl(n);
  sl[n - 1] = false;
  for (int i = n - 2; i >= 0; --i) {
    sl[i] = (vec[i] > vec[i + 1] || (vec[i] == vec[i + 1] && sl[i + 1]));
    if (sl[i] && !sl[i + 1])
      lms_idx.push_back(i + 1);
  }
  std::reverse(lms_idx.begin(), lms_idx.end());
  induced_sort(vec, val_range, SA, sl, lms_idx);
  std::vector<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size());
  for (int i = 0, k = 0; i < n; ++i)
    if (!sl[SA[i]] && SA[i] >= 1 && sl[SA[i] - 1]) {
      new_lms_idx[k++] = SA[i];
    }
  int cur = 0;
  SA[n - 1] = cur;
  for (size_t k = 1; k < new_lms_idx.size(); ++k) {
    int i = new_lms_idx[k - 1], j = new_lms_idx[k];
    if (vec[i] != vec[j]) {
      SA[j] = ++cur;
      continue;
    }
    bool flag = false;
    for (int a = i + 1, b = j + 1;; ++a, ++b) {
      if (vec[a] != vec[b]) {
        flag = true;
        break;
      }
      if ((!sl[a] && sl[a - 1]) || (!sl[b] && sl[b - 1])) {
        flag = !((!sl[a] && sl[a - 1]) && (!sl[b] && sl[b - 1]));
        break;
      }
    }
    SA[j] = (flag ? ++cur : cur);
  }
  for (size_t i = 0; i < lms_idx.size(); ++i)
    lms_vec[i] = SA[lms_idx[i]];
  if (cur + 1 < lms_idx.size()) {
    auto lms_SA = SA_IS(lms_vec, cur + 1);
    for (size_t i = 0; i < lms_idx.size(); ++i) {
      new_lms_idx[i] = lms_idx[lms_SA[i]];
    }
  }
  induced_sort(vec, val_range, SA, sl, new_lms_idx);
  return SA;
}
std::vector<int> LCP(const std::vector<int> &s, const std::vector<int> &sa) {
  int n = s.size(), k = 0;
  std::vector<int> lcp(n), rank(n);
  for (int i = 0; i < n; i++)
    rank[sa[i]] = i;
  for (int i = 0; i < n; i++, k ? k-- : 0) {
    if (rank[i] == n - 1) {
      k = 0;
      continue;
    }
    int j = sa[rank[i] + 1];
    while (i + k < n && j + k < n && s[i + k] == s[j + k])
      k++;
    lcp[rank[i]] = k;
  }
  lcp[n - 1] = 0;
  return lcp;
}
std::vector<int> suffix_array(const std::vector<int> &a) {
  auto [mn, mx] = std::minmax_element(a.begin(), a.end());
  std::vector<int> vec(a.size() + 1);
  std::copy(a.begin(), a.end(), vec.begin());
  for (auto &x : vec) {
    x -= *mn - 1;
  }
  vec.back() = 0;
  auto ret = SA_IS(vec, *mx - *mn + 3);
  ret.erase(ret.begin());
  return ret;
}

void work() {
  int n;
  std::cin >> n;
  std::vector<int> a;
  std::vector<int> start, end;
  for (int i = 0; i < n; ++i) {
    std::string str;
    std::cin >> str;
    start.emplace_back(a.size());
    for (auto &c : str) {
      a.emplace_back(c);
    }
    end.emplace_back(a.size());
    a.emplace_back(-i);
  }
  std::vector<int> sa = suffix_array(a);
  std::vector<int> height = LCP(a, sa);

  std::vector<int> id, idx, len, lcp;
  for (int i = n; i < a.size(); ++i) {
    int j = std::lower_bound(end.begin(), end.end(), sa[i]) - end.begin();
    id.emplace_back(j);
    idx.emplace_back(sa[i] - start[j]);
    len.emplace_back(end[j] - sa[i]);
    lcp.emplace_back(height[i]);
  }
  int m = id.size();

  std::vector<int> l(m - 1, -1), r(m - 1, -1);
  int root = -1;
  {
    std::stack<int> s;
    for (int i = 0; i + 1 < m; ++i) {
      while (!s.empty() && lcp[s.top()] > lcp[i]) {
        l[i] = s.top();
        s.pop();
      }
      if (!s.empty()) {
        r[s.top()] = i;
      }
      s.push(i);
    }
    while (!s.empty()) {
      root = s.top();
      s.pop();
    }
  }

  int q;
  std::cin >> q;
  std::vector<std::pair<int64, int>> queries(q);
  std::vector<std::tuple<int, int, int>> res(q);
  for (int i = 0; i < q; ++i) {
    std::cin >> queries[i].first;
    --queries[i].first;
    queries[i].second = i;
  }
  std::sort(queries.begin(), queries.end());
  int cur = 0;
  int64 num = 0;
  auto dfs = [&](auto dfs, int x, int L, int R, int w) {
    if (L > R) {
      return;
    }
    int range = R - L + 1;
    int sz = x == -1 ? len[L] : lcp[x];
    int64 delta = 1LL * range * (sz - w);
    while (cur < q && num + delta > queries[cur].first) {
      int64 req = queries[cur].first - num;
      auto &ans = res[queries[cur].second];
      std::get<0>(ans) = id[L + req % range];
      std::get<1>(ans) = idx[L + req % range];
      std::get<2>(ans) = w + req / range;
      ++cur;
    }
    num += delta;
    if (x != -1) {
      dfs(dfs, l[x], L, x, lcp[x]);
      dfs(dfs, r[x], x + 1, R, lcp[x]);
    }
  };
  dfs(dfs, root, 0, m - 1, 0);
  for (int i = 0; i < q; ++i) {
    auto [k, l, r] = res[i];
    printf("%d %d %d\n", k + 1, l + 1, l + r + 1);
  }
}

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

  int T = 1;
  // std::cin >> T;
  while (T--) {
    work();
  }
  return 0;
}