ICPC22-Southern-J-Not_A_Classic_string_problem

#include <bits/stdc++.h>
#define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
#define down(i,a,b) for (int i = (int)a; i >= (int)b; i--)
#define pii pair<int, int>
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;

const int maxn = 4e5 + 10;
const int maxq = 5e5 + 10;
const int LOG = log2(maxn)+2;
int n;

int SA[maxn];
int LCP[maxn];
int pos[maxn];

pair<pii, int> L[maxn]; //Lexicography order: of string at position have rank i -> start at position L[i].second
int R[LOG][maxn]; //Ranking of string start at position i, have length of 2^log -> have rank R[log][i]


void build_SA(const string& s){
    up(i,1,n) R[0][i] = s[i];

    for (int POW = 1; (1 << (POW-1)) <= n; POW++){
        up(i,1,n){
            L[i].f.f = R[POW-1][i];
            int k = i + (1 << (POW-1));
            if (k <= n) L[i].f.s = R[POW-1][k];
            else L[i].f.s = -1;
            L[i].s = i;
        }
        sort(L+1, L+n+1);

        int cnt = 0;
        up(i,1,n){
            if (L[i].f == L[i-1].f) R[POW][L[i].s] = R[POW][L[i-1].s];
            else R[POW][L[i].s] = ++cnt;
        }
    }

    up(i,1,n) SA[i] = L[i].s;
}


void Kasai(const int SA[], const string& s){
    up(i,1,n) pos[SA[i]] = i;

    int k = 0;
    up(i,1,n){
        int& cur = pos[i];
        int j = SA[cur-1];
        while (i+k <= n && j+k <= n && s[i+k] == s[j+k]) ++k;
        LCP[cur] = k;
        if (k) --k;
    }
}

vector<int> Group[maxn];
int lmost[maxq], rmost[maxq];
struct Query{
    int U,V,slen;
} Q[maxq];

void build_lmost(){
    deque<pii> DQ;
    up(i,1,n){
        while (!DQ.empty() && DQ.back().f >= LCP[i]) DQ.pop_back();
        DQ.push_back(make_pair(LCP[i], i));
        for (auto id : Group[i]){
            int x = lower_bound(all(DQ), make_pair(Q[id].slen, -1)) - DQ.begin();
            if (x == 0) lmost[id] = 1;
            else lmost[id] = DQ[x-1].second;
        }
    }
}

void build_rmost(){
    deque<pii> DQ;
    down(i,n,1){
        while (!DQ.empty() && DQ.back().f >= LCP[i]) DQ.pop_back();
        DQ.push_back(make_pair(LCP[i], i));
        for (auto id : Group[i-1]){
            int x = lower_bound(all(DQ), make_pair(Q[id].slen, -1)) - DQ.begin();
            if (x == 0) rmost[id] = n;
            else rmost[id] = DQ[x-1].second - 1;
        }
    }
}

int BIT[maxn];
void update(int x, const int val){
    for (; x <= n; x += (x & (-x))) BIT[x] += val;
}
int get(int x){
    int res = 0;
    for (; x; x -= (x & (-x))) res += BIT[x];
    return res;
}

struct event{
    int L,R,id,SIGN;
    event(int L, int R, int id, int SIGN):
        L(L), R(R), id(id), SIGN(SIGN)
    {}
};
vector<event> E[maxn];

int ans[maxq];
void solve(){
    up(i,1,n){
        update(SA[i], 1);
        for (auto e : E[i]){
            int L = e.L;
            int R = e.R;
            int id = e.id;
            int SIGN = e.SIGN;
            ans[id] += SIGN * (get(R) - get(L-1));
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string s,t;
    cin >> s >> t;
    int SSIZE = s.size();

    string g = "@" + s + t;
    n = g.size() - 1;

    build_SA(g);
    Kasai(SA, g);

    int q;
    cin >> q;
    up(i,1,q){
        int sl, sr, tl, tr;
        cin >> sl >> sr >> tl >> tr;
        int slen = sr - sl + 1;
        Q[i] = {tl, tr, slen};

        Group[pos[sl]].emplace_back(i);
        lmost[i] = rmost[i] = pos[sl];
    }

    build_lmost();
    build_rmost();

    up(i,1,q){
        int L = lmost[i]; //find left most possible position lmost[i] such that LCP from lmost[i] to i exists
        int R = rmost[i]; //find right most possible position rmost[i] such that LCP from i to rmost[i] exists
        int A = Q[i].U + SSIZE; //Find lowerbound limit value of the suffix string in the "@+s+t"
        int B = Q[i].V + SSIZE - Q[i].slen + 1; //Find upperbound limit value of the suffix string in the "@+s+t"

        if (B < A || R < L) continue;
        E[L-1].emplace_back(event(A, B, i, -1));
        E[R].emplace_back(event(A, B, i, 1));
    }

    solve();
    up(i,1,q) cout << ans[i] << "\n";
}