【Codeforces 547E】Mike and Friends | Mrsrz's blog

后缀数组，二维数点

题目大意：

给定 $n$ 个字符串 $s_1,s_2,s_3,\dots,s_n$。每次询问给出 $l,r,k$，问 $s_k$ 在 $s_{l\sim r}$ 中的出现次数。

题解：

将所有串拼起来后求出后缀数组，记录每个位置属于哪个串。

对每个询问，我们 ST 表+二分，求出两个端点 $L,R$ 表示后缀数组上 $L\sim R$ 的位置代表的后缀包含该串。

然后就是找后缀数组上位置在 $L\sim R$ 内，且属于的串在 $l\sim r$ 的点的个数。

二维数点问题，离线树状数组即可。

时间复杂度 $O((n+m)\log n)$。

Code：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define lg(x)(31-__builtin_clz(x))
const int N=5e5+5;
int s[N],len,n,Len[N],pos[N],m,bel[N];
int c[N],x[N],y[N],sa[N],height[N];
int __=233;
char t[N];
int st[20][N];
inline int lcp(int l,int r){
    if(++l>r)return len;
    const int g=lg(r-l+1);
    return min(st[g][l],st[g][r-(1<<g)+1]);
}
void sort_(){
    int m=__;
    for(int i=1;i<=len;++i)++c[x[i]=s[i]];
    for(int i=1;i<=m;++i)c[i]+=c[i-1];
    for(int i=len;i;--i)sa[c[x[i]]--]=i;
    for(int k=1;k<=len;k<<=1){
        int p=0;
        for(int i=len-k+1;i<=len;++i)y[++p]=i;
        for(int i=1;i<=len;++i)
        if(sa[i]>k)y[++p]=sa[i]-k;
        for(int i=1;i<=m;++i)c[i]=0;
        for(int i=1;i<=len;++i)++c[x[i]];
        for(int i=1;i<=m;++i)c[i]+=c[i-1];
        for(int i=len;i;--i)sa[c[x[y[i]]]--]=y[i];
        swap(x,y);
        x[sa[p=1]]=1;
        for(int i=2;i<=len;++i)
        x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p);
        if(p==len)break;
        m=p;
    }
    for(int i=1,k=0;i<=len;++i)
    if(x[i]!=1){
        k-=!!k;
        int j=sa[x[i]-1];
        while(s[i+k]==s[j+k])++k;
        height[x[i]]=k;
    }
    for(int i=1;i<=len;++i)st[0][i]=height[i];
    for(int j=1;j<20;++j)
        for(int i=1;i+(1<<j-1)<=len;++i)
            st[j][i]=min(st[j-1][i],st[j-1][i+(1<<j-1)]);
}
inline int askL(int pos,int len){
    int l=1,r=pos-1,ret=pos;
    while(l<=r){
        const int mid=l+r>>1;
        if(lcp(mid,pos)>=len)r=(ret=mid)-1;else l=mid+1;
    }
    return ret;
}
inline int askR(int pos,int len){
    int l=pos+1,r=::len,ret=pos;
    while(l<=r){
        const int mid=l+r>>1;
        if(lcp(pos,mid)>=len)l=(ret=mid)+1;else r=mid-1;
    }
    return ret;
}
struct info{
    int l,r,id,fh;
};
vector<info>vec[N];
long long ans[N];
int B[N];
inline void add(int i){for(;i<=len;i+=i&-i)++B[i];}
inline int ask(int i){int x=0;for(;i;i&=i-1)x+=B[i];return x;}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>t;
        pos[i]=len+1;
        Len[i]=strlen(t);
        for(int j=0;t[j];++j)
        s[++len]=t[j],bel[len]=i;
        if(i!=n)s[++len]=++__;
    }
    sort_();
    for(int i=1;i<=m;++i){
        int k,l,r;
        cin>>l>>r>>k;
        int L=askL(x[pos[k]],Len[k]),R=askR(x[pos[k]],Len[k]);
        vec[R].push_back((info){l,r,i,1});
        vec[L-1].push_back((info){l,r,i,-1});
    }
    for(int i=1;i<=len;++i){
        if(bel[sa[i]])add(bel[sa[i]]);
        for(auto f:vec[i])
        ans[f.id]+=f.fh*(ask(f.r)-ask(f.l-1));
    }
    for(int i=1;i<=m;++i)
    cout<<ans[i]<<'\n';
    return 0;
}