# ICPC22-Southern-J-Not_A_Classic_string_problem

no RMQ, no sort offline query
unknown
c_cpp
19 days ago
4.3 kB
5
Indexable
Never
```#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";
}
```