QUESTION

Jimmy loves playing with strings. He thinks string A is similar to string B if the following conditions are satisfied:\n\n1.Both strings have the same length (i.e.,A=a0 a1..an-1 and B=b0 b1..bn-1 ).\n2. For each valid pair of indices,(ij) , in the strings,[ai=aj and bi=bj] or [ai=!=aj and bi!=bj].\nHe has string, S, size of n and gives you q queries to answer where each query is in the form of a pair of integers (li, ri). For each substring S[li,ri], find the number of substrings S[x,y] where substring S[li,ri] is similar to substring and print this number on a new line.\n\nNote: Substring S[x,y] is the contiguous sequence of characters from index x to index y. For example, if S=abcdefgh, then S[3,6]=cdef.\n\nInput Format\n\nThe first line contains two space-separated integers describing the respective values of n and q. \nThe second line contains string S. \nEach line i of the q subsequent lines contains two space-separated integers describing the respective values of li and ri for query i.\n\nConstraints\n1. 1<=n, q<=5×10^4 2. 1<=Li<=Ri<=n 3. si E {a,b,c,d,e,f,g,h,i,j}\nOutput Format\n\nFor each query, print the number of similar substrings on a new line.

ANSWER

#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int SIZE = 5e4+10;
const int MAXLEN = SIZE*20;
int emp;
char s[MAXLEN];
int SA[MAXLEN],H[MAXLEN],RANK[MAXLEN];


int nxt_lv[20][MAXLEN],rp[MAXLEN];
int st[SIZE];
int tmp[MAXLEN], num[MAXLEN],d[MAXLEN];
void SuffixArray(int text[], int t[], int n, int m) {
    REP(i,n) t[i] = i,d[i]=text[i];
    for (int i = 1, it=0; i < n; i *= 2, it++) {
        if(it){
            REP(j,n)
                nxt_lv[it][j]=nxt_lv[it-1][nxt_lv[it-1][j]];
        }
        //rsort(s+i, t, tmp, n, m);
        REP(j,m+1)num[j]=0;
        REP(j,n){
            num[d[nxt_lv[it][t[j]]]]++;
            //assert(d[nxt_lv[it][j]]!=0);
        }
        REP(j,m)num[j+1]+=num[j];
        REP(j,n)tmp[num[d[nxt_lv[it][t[j]]]-1]++]=t[j];
        //rsort(s, tmp, t, n, m);
        REP(j,m+1)num[j]=0;
        REP(j,n){
            num[d[tmp[j]]]++;
            //assert(d[j]!=0);
        }
        REP(j,m)num[j+1]+=num[j];
        REP(j,n)t[num[d[tmp[j]]-1]++]=tmp[j];
        REP(j,n) tmp[j] = d[j];
        m=1;
        REP(j,n){
            d[t[j]] = m;
            if (tmp[t[j]] != tmp[t[j+1]] || tmp[nxt_lv[it][t[j]]] != tmp[nxt_lv[it][t[j+1]]])m++;
        }
    }
}

int nxt_pos[SIZE],lt_pos[SIZE],cn;
int get_val(int x,int len){
    if(lt_pos[x+len]<x)return emp;
    return x+len-lt_pos[x+len];
}
int main(){
    DRII(n,q);
    emp=n+1;
    cn=n+1;
    RS(s);
    REP(i,n){
        nxt_lv[0][i]=i+1;
        s[i]-='a';
    }
    nxt_lv[0][n]=n;
    rp[n]=1;
    {
        MS1(lt_pos);
        int now[10]={};
        MS1(now);
        for(int i=n-1;i>=0;i--){
            if(now[s[i]]!=-1){
                lt_pos[now[s[i]]]=i;
                nxt_pos[i]=now[s[i]];
                rp[now[s[i]]]=now[s[i]]-i+1;
            }
            now[s[i]]=i;
        }
        REP(i,10)
            if(now[i]!=-1)rp[now[i]]=emp;
    }
    {
        VI now(n+1);
        REP(i,n+1)now[i]=i;
        REP(i,n-1){
            if(nxt_pos[i]){
                REPP(j,i+1,nxt_pos[i]){
                    rp[cn]=rp[now[j]];
                    now[j]=cn++;
                }
                now[nxt_pos[i]]=cn;
                rp[cn++]=emp;
                REPP(j,i+1,nxt_pos[i]+1)
                    nxt_lv[0][now[j]]=now[j+1];
            }
            st[i+1]=now[i+1];
        }
    }
    SuffixArray(rp,SA,cn,emp);
    REP(i,cn)RANK[SA[i]]=i;
    VPII pp;
    REP(i,n)
        pp.PB(MP(RANK[st[i]],i));
    sort(ALL(pp));
    REP(i,n){
        RANK[pp[i].S]=i;
        SA[i]=pp[i].S;
    }
    //REP(i,n)printf("%d,",SA[i]);
    //puts("");
    REP(k,n-1){
        int len=0;
        int i=SA[k];
        int j=SA[k+1];
        while(max(i,j)+len<n&&get_val(i,len)==get_val(j,len))len++;
        H[k]=len;
    }
    while(q--){
        DRII(x,h);x--;
        h-=x;
        int mid=RANK[x];
        int an=1;
        REPP(i,mid,n-1){
            if(H[i]>=h)an++;
            else break;
        }
        for(int i=mid-1;i>=0;i--){
            if(H[i]>=h)an++;
            else break;
        }
        printf("%d\n",an);
    }
    return 0;
}