sam+线段树合并+倍增

TLE on TEST 41

别人都跑几百 $ms$，为什么我还在 T/kel

#include <bits/stdc++.h>
using namespace std;
namespace Le0{
#define pii pair<int,int>
#define fi first
#define se second
const int N=1.1e6+6;
string s;
int n,Q;
struct seg{
    int nt=0;
    pii t[N*21];
    int ch[N*21][2];
    inline pii pushup(pii p1,pii p2){ 
        if(p1.fi>=p2.fi) return p1;
        return p2;
    }
    inline void pp(int p){
        if(!ch[p][0]) t[p]=t[ch[p][1]];
        if(!ch[p][1]) t[p]=t[ch[p][0]];
        t[p]=pushup(t[ch[p][0]],t[ch[p][1]]);
    }
    inline void modify(int &p,int l,int r,int x,int k){
        if(!p) p=++nt;
        if(l==r){
            t[p].fi=k;t[p].se=l;
            return ;
        }
        int mid=l+r>>1;
        if(x<=mid) modify(ch[p][0],l,mid,x,k);
        else modify(ch[p][1],mid+1,r,x,k);
        pp(p);
    }
    inline int merge(int p1,int p2,int l,int r){
        if(!p1||!p2) return p1+p2;
        int p=++nt;
        if(l==r){
            t[p]=t[p1];
            t[p].fi+=t[p2].fi;
            return p;
        }
        int mid=l+r>>1;
        ch[p][0]=merge(ch[p1][0],ch[p2][0],l,mid);
        ch[p][1]=merge(ch[p1][1],ch[p2][1],mid+1,r);
        pp(p);
        return p;
    }
    inline pii query(int p,int l,int r,int ql,int qr){
        if(!p) return {0,ql};
        if(l==r){
            return t[p];
        }
        int mid=l+r>>1;
        if(qr<=mid) return query(ch[p][0],l,mid,ql,qr);
        if(ql>mid) return query(ch[p][1],mid+1,r,ql,qr);
        return pushup(query(ch[p][0],l,mid,ql,qr),query(ch[p][1],mid+1,r,ql,qr));
    }
}sg;
struct node{
    int len,id;
}q[N];
inline bool cmp(node a,node b){
    return a.len>b.len;
}
struct sam{
    int nt=1;
    int son[N][26],fa[N],rt[N],len[N],st[N][21],ed[N];
    inline int build(int c,int las,vector<int> &vis,int dep){
        int q=++nt,p=las;
        len[q]=len[p]+1;
        for(int x:vis){
            sg.modify(rt[q],1,n+1,x,1);
        }
        for(;p&&!son[p][c];p=fa[p]) son[p][c]=q;
        if(!p) fa[q]=1;
        else{
            int x=son[p][c];
            if(len[x]==len[p]+1) fa[q]=x;
            else{
                int y=++nt;
                fa[y]=fa[x];
                fa[x]=fa[q]=y;
                memcpy(son[y],son[x],sizeof(son[x]));
                len[y]=len[p]+1;
                for(;p&&son[p][c]==x;p=fa[p]) son[p][c]=y;
            }
        }
        if(dep) ed[dep]=q;
        return q;
    }
    inline void work(){
        for(int i=1;i<=nt;i++){
            q[i]=(node){len[i],i};
        }
        sort(q+1,q+1+nt,cmp);
        for(int i=1;i<nt;i++){
            int x=q[i].id;
            st[x][0]=fa[x];
            rt[fa[x]]=sg.merge(rt[fa[x]],rt[x],1,n+1);
        }
        for(int j=1;j<=20;j++){
            for(int i=1;i<=nt;i++){
                st[i][j]=st[st[i][j-1]][j-1];
            }
        }
    }
    inline int getnode(int l,int r){
        int x=ed[r];
        for(int i=20;i>=0;i--){
            while(st[x][i]>1&&len[st[x][i]]>=r-l+1) x=st[x][i];
        }
        return x;
    }
    inline void qry(int x,int y,int l,int r){
        int p=getnode(l,r);
        auto as=sg.query(rt[p],1,n+1,x,y);
        cout<<as.se<<" "<<as.fi<<"\n";
    }
}sm;
struct trie{
    int nt=1;
    int son[N>>1][26],pos[N>>1],dep[N>>1];
    vector<int> vis[N>>1];
    inline void build(string s,int id){
        int l=s.size(),p=1;
        for(int i=0;i<l;i++){
            if(!son[p][s[i]-'a']) son[p][s[i]-'a']=++nt;
            p=son[p][s[i]-'a'];
            vis[p].push_back(id);
            if(id==n+1) dep[p]=i+1;
        }
    }
    inline void work(){
        queue<int> q;
        q.push(1);
        pos[1]=1;
        while(q.size()){
            int x=q.front();q.pop();
            for(int i=0;i<26;i++){
                if(son[x][i]){
                    int y=son[x][i];
                    q.push(y);
                    pos[y]=sm.build(i,pos[x],vis[y],dep[y]);
                }
            }
        }
    }
}tr;
int main(){
    cin>>s>>n;
    tr.build(s,n+1);
    for(int i=1;i<=n;i++){
        cin>>s;
        tr.build(s,i);
    }
    tr.work();
    sm.work();
    cin>>Q;
    while(Q--){
        int x,y,l,r;
        cin>>x>>y>>l>>r;
        sm.qry(x,y,l,r);
    }
    return 0;
}
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    return Le0::main();
}