Sorting Segments

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

using i64 = long long;

const int INF = 0x3f3f3f3f;

template<class T>
class SegmentTree {
    struct Node {
        T val;
        Node(T x) : val(x) {}
        Node () : val(INF) {}
    };
    int N;
    std::vector<T> a;
    std::vector<Node> tr;
    Node neutral;
    inline Node join(const Node &a, const Node &b) {
        return Node(min(a.val, b.val));
    }
    void build(int node, int l, int r) {
        if (l == r) {
            tr[node] = Node(a[l]);
            return;
        }
        int mid = l+(r-l)/2, lc = (node << 1);
        build(lc, l, mid);
        build(lc+1, mid+1, r);
        tr[node] = join(tr[lc], tr[lc+1]);
    }
    Node query(int node, int l, int r, int ql, int qr) {
        if (r < l or qr < l or r < ql) return neutral;
        if (ql <= l and r <= qr) return tr[node];
        int mid = l+(r-l)/2, lc = (node << 1);
        return join(query(lc, l, mid, ql, qr),
                    query(lc+1, mid+1, r, ql, qr));
    }
public:
    template<class MyIterator>
    SegmentTree (MyIterator begin, MyIterator end) {
        N = end-begin-1;
        tr.assign(4*N, 0);
        a = std::vector<T>(begin, end);
        build(1, 1, N);
    }
    SegmentTree (int n) : N(n) {
        tr.assign(4*N, 0);
        a.assign(N+1, 0);
    }
    T query(int l, int r) {
        return query(1, 1, N, l+1, r+1).val;
    }
};

vector<int> sort_cyclic_shifts(const string& s) {
  int n = s.size();
  const int alphabet = 256;

    vector<int> p(n), c(n), cnt(max(alphabet, n), 0);
    for (int i = 0; i < n; i++)
        cnt[s[i]]++;
    for (int i = 1; i < alphabet; i++)
        cnt[i] += cnt[i-1];
    for (int i = 0; i < n; i++)
        p[--cnt[s[i]]] = i;
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; i++) {
        if (s[p[i]] != s[p[i-1]])
            classes++;
        c[p[i]] = classes - 1;
    }

    vector<int> pn(n), cn(n);
    for (int h = 0; (1 << h) < n; ++h) {
        for (int i = 0; i < n; i++) {
            pn[i] = p[i] - (1 << h);
            if (pn[i] < 0)
                pn[i] += n;
        }
        fill(cnt.begin(), cnt.begin() + classes, 0);
        for (int i = 0; i < n; i++)
            cnt[c[pn[i]]]++;
        for (int i = 1; i < classes; i++)
            cnt[i] += cnt[i-1];
        for (int i = n-1; i >= 0; i--)
            p[--cnt[c[pn[i]]]] = pn[i];
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; i++) {
            pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
            pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
            if (cur != prev)
                ++classes;
            cn[p[i]] = classes - 1;
        }
        c.swap(cn);
    }
    return p;
}

vector<int> suffix_array_construction(string s) {
  s += "$";
  vector<int> sorted_shifts = sort_cyclic_shifts(s);
  sorted_shifts.erase(sorted_shifts.begin());
  return sorted_shifts;
}

vector<int> lcp_construction(string const& s, vector<int> const& p) {
  int n = s.size();
  vector<int> rank(n, 0);
  for (int i = 0; i < n; i++)
      rank[p[i]] = i;

  int k = 0;
  vector<int> lcp(n-1, 0);
  for (int i = 0; i < n; i++) {
      if (rank[i] == n - 1) {
          k = 0;
          continue;
      }
      int j = p[rank[i] + 1];
      while (i + k < n && j + k < n && s[i+k] == s[j+k])
          k++;
      lcp[rank[i]] = k;
      if (k)
          k--;
  }
  return lcp;
}

int n;

int main() {
  cin.tie(0)->sync_with_stdio(0);

  string s; cin >> s;

  n = s.size();

  if (n == 1) {
    int m; cin >> m;
    while (m--) {
      int l, r; cin >> l >> r;
      cout << l << ' ' << r << '\n';
    }

    return 0;
  }

  vector<int> SA = suffix_array_construction(s);
  vector<int> lcp = lcp_construction(s, SA);

  lcp.insert(lcp.begin(), 0);
  SegmentTree<int> ST(lcp.begin(), lcp.end());

  vector<pair<int, int>> v;

  int m; cin >> m;
  while (m--) {
    int l, r; cin >> l >> r, --l, --r;
    v.push_back({l, r});
  }

  vector<int> rank(n, 0);
  for (int i = 0; i < n; ++i) {
    rank[SA[i]] = i;
  }

  sort(v.begin(), v.end(), [&](pair<int, int> a, pair<int, int> b) {
    int sza = a.se - a.fi + 1, szb = b.se - b.fi + 1;

    int k = rank[a.fi] == rank[b.fi]
      ? min(sza, szb)
      : (rank[a.fi] < rank[b.fi]
        ? ST.query(rank[a.fi], rank[b.fi] - 1)
        : ST.query(rank[b.fi], rank[a.fi] - 1));

    k = min({ k, sza, szb });

    if (k == sza and k == szb)
      return a < b;
    if (k == sza or k == szb)
      return k == sza;

    char ca = s[a.fi + k], cb = s[b.fi + k];

    return ca < cb;
  });

  for (auto [a, b] : v) {
    cout << 1+a << " " << 1+b << '\n';
  }
}