C++(clang++ 11.0.1) 解法, 执行用时: 421ms, 内存消耗: 127716K, 提交时间: 2022-08-03 17:47:57

#include<bits/stdc++.h>
#define pw(a) (1LL<<(a))
// #define L ((p)<<1)
// #define R ((p)<<1|1)
#define endl '\n'
using namespace std;
 
typedef long long LL;
typedef double DD;
typedef pair<int,int> PR;
 
const int inf=0x3f3f3f3f;
const int mod=998244353;
const int N=5e5+10;
 
int n,m,k,t;
int node[N],w[N];
struct SAM
{
    int len,f;
    int son[26];
}sam[N];
int las=1,tot=1;
int insert(int x)
{
    int p=las,np=las=++tot;
    sam[np].len=sam[p].len+1;
    while(p and !sam[p].son[x]) sam[p].son[x]=np,p=sam[p].f;
    if(!p) sam[np].f=1;
    else
    {
        int q=sam[p].son[x];
        if(sam[q].len==sam[p].len+1) sam[np].f=q;
        else
        {
            int nq=++tot;
            sam[nq]=sam[q];
            sam[nq].len=sam[p].len+1;
            sam[np].f=sam[q].f=nq;
            while(p and sam[p].son[x]==q) sam[p].son[x]=nq,p=sam[p].f;
        }
    }
    return np;
}
char s[N];
vector<int>adj[N];
int f[N][20];
void dfs(int u)
{
    f[u][0]=sam[u].f;
    for(int i=1;i<=19;i++) f[u][i]=f[f[u][i-1]][i-1];
    for(int x:adj[u]) dfs(x);
}
int tre[N];
void update(int x)
{
    for(int i=x;i<=n;i+=i&-i) tre[i]++;
}
int query(int x)
{
    int res=0;
    for(int i=x;i>=1;i-=i&-i) res+=tre[i];
    return res;
}
int query(int l,int r)
{
    if(l>r) return 0;
    return query(r)-query(l-1);
}
vector<array<int,3>>Q[N];
int ans[N];
void DFS(int u)
{
    for(auto [l,r,num]:Q[u]) ans[num]-=query(l,r);
    if(w[u]) update(w[u]);
    for(int x:adj[u]) DFS(x);
    for(auto [l,r,num]:Q[u]) ans[num]+=query(l,r);
}
signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>s+1;
    n=strlen(s+1);
    for(int i=1;i<=n;i++) node[i]=insert(s[i]-'a'),w[node[i]]=i;
    for(int i=1;i<=tot;i++) adj[sam[i].f].push_back(i);
    dfs(1);
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int l,r,L,R;
        cin>>l>>r>>L>>R;
        int u=node[r];
        for(int i=19;i>=0;i--)
        {
            if(sam[f[u][i]].len>=r-l+1) u=f[u][i];
        }
        Q[u].push_back({L+r-l,R,i});
    }
    DFS(1);
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';cout<<endl;
    return 0;
}