C. Sorting Substrings2

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

typedef pair<int, int> ii;
#define S second
#define F first

vector< vector< int > > Rank;
map< ii , int > Cnt;
vector< ii > Seg;
string s;
int n ,q;

inline string Read()
{
    const int N = 4e5+5;
    static char Buff[N];
    scanf("\n%s",Buff);
    return Buff;
}

void CountSort(vector< int > &SA ,vector< int > &RA ,int k ,int n)
{
    int N = max(300,n);
    vector< int > Cnt(N,0);
    vector< int > tempSA(n);

    for(int i = 0 ; i < n ; i++)
        Cnt[ (i + k >= n) ? 0 : RA[i + k] ] ++;

    for(int i = 0, sum = 0 ; i < N ; i++)
    {
        int t  = Cnt[i];
        Cnt[i] = sum;
        sum   += t;
    }

    for(int i = 0 ; i < n ; i++)
        tempSA[ Cnt[ ((SA[i] + k) < n) ? RA[ SA[i] + k ] : 0] ++ ] = SA[i];

    SA = tempSA;
}

void RadixSort(vector< int > &SA ,vector< int > &RA ,int s ,int f ,int n)
{
    CountSort(SA ,RA ,s ,n);
    CountSort(SA ,RA ,f ,n);
}

vector< vector< int > > ConstructSA(string &s ,int n)
{
    vector< vector< int > > Rank((int)log2(n) + 2 ,vector< int >(n));

    vector< int > tempRA(n ,0) ,RA(n ,0) ,SA(n ,0);

    for(int i = 0 ; i < n ; i++) RA[i] = (int)s[i];
    for(int i = 0 ; i < n ; i++) SA[i] = i;

    for(int k = 1 ; k < n && (RA[ SA[n - 1] ] != n - 1) ; k <<= 1 )
    {
        RadixSort(SA ,RA ,k ,0 ,n);

        int r = tempRA[ SA[0] ] = 0;
        for(int i = 1 ; i < n ; i++)
        {
            bool flagF = (RA[ SA[i] ] == RA[ SA[i - 1] ]);
            bool flagS = (RA[ (SA[i] + k) >= n ? 0 : SA[i] + k ] ==
                          RA[ (SA[i - 1] + k) >= n ? 0 : SA[i - 1] + k ]);

            tempRA[ SA[i] ] = (flagF && flagS) ? r : ++r;
        }

        Rank[ (int)log2(k) ] = RA = tempRA;
    }

    return Rank;
}

inline int Calc(int i, int j, int Len ,int Log)
{
    ii a = ii( Rank[Log][i] , Rank[Log][ ( i + Len - (1 << Log) ) % n ] );
    ii b = ii( Rank[Log][j] , Rank[Log][ ( j + Len - (1 << Log) ) % n ] );
    return (a == b ? 0 : a < b ? -1 : 1);
}

inline bool Cmp(const ii &a ,const ii &b){
    int LenA = a.S - a.F + 1;
    int LenB = b.S - b.F + 1;
    int Len  = min(LenA ,LenB);
    int Log  = log2(Len);

    int Res = Calc(a.F ,b.F ,Len ,Log);

    if( Res == +1 ) return false;
    if( Res == -1 ) return true;

    if( LenA > LenB ) return false;
    if( LenA < LenB ) return true;

    return a < b;
}

int main()
{
    n = (int)(s = Read() + ' ').size();

    scanf("%d" ,&q);
    for(int i = 0 ; i < q ; i++)
    {
        int L;  scanf("%d" ,&L) ,L --;
        int R;  scanf("%d" ,&R) ,R --;

        ii x = ii(L ,R);
        if( Cnt[x] == 0 ) Seg.push_back(x);
        Cnt[x] += 1;
    }

    Rank = ConstructSA(s ,n);

    sort(Seg.begin() ,Seg.end() ,Cmp); cout << endl;

    for(auto i : Seg) while( Cnt[i]-- ) printf("%d %d\n" ,i.F + 1 ,i.S + 1);
}