[Codeforces 547E]Mike and Friends

如果要看懂這個題解，必須先了解「後綴陣列和其衍生的$height$陣列」的性質

這裡的詢問很特別，要你算出第$l$到第$r$隻熊會打給第$k$隻熊幾次
我們可以反向思考，怎麼求出第$k$隻熊會被哪幾隻熊打電話呢？

說明：
$phone[i]$為第$i$隻熊的電話代表的字串

可以考慮把所有熊的電話號碼接起來 (稱新字串為$S$)，中間用空字元隔開
如果我們對$S$建立它的後綴陣列和其衍生的$height$陣列
那麼對於第$k$隻熊，會打電話給它的就是$height$陣列中連續高度$\geq \left|phone[k]\right|$的區間$_{(tag\ 1)}$了
利用後綴陣列來代出這個區間中的每個點分別對應到$S$的哪些位置，就能知道是哪幾隻熊打幾次電話給它了！

可是一個一個代出是哪隻熊打的電話，再篩選出第$l$到第$r$隻熊，實在太花時間了
我們可以考慮離線作法
可以發現，對於$height$陣列的一個區間$[l_{h},r_{h}]$，我們可以用「($height$中區間$[1,r_{h}]$有幾隻是第$l$到第$r$隻熊)$-$($height$中區間$[1,l_{h}-1]$有幾隻是第$l$到第$r$隻熊)」來算出$height$中區間$[l_{h},r_{h}]$有幾隻是第$l$到第$r$隻熊

因此，我們可以把所有的詢問分割成一個個形如「$height$中區間$[1,x]$有幾隻是第$l$到第$r$隻熊」的子問題，將這些子問題依照$x$排序，然後讓$i$由小到大跑，將$height[i]$在$S$上對應到的位置加進線段樹中維護
這樣對於每個子問題，$i$跑到$x$時，就可以直接利用線段樹的區間查詢，求出$[l,r]$有幾隻熊了

每個詢問的答案就是它對應到的兩個子問題答案相減

$Tags$：
$_{tag\ 1}$：將每隻熊的電話號碼由長到短排序，$height$由大到小排序，然後就可以在$x$遞減的情況下，利用$disjoint\ sets$維護$height$上高度$\geq x$的連通塊，當$x$等於第$k$熊的電話號碼長度時，就可以直接利用$disjoint\ sets$求出所在連通塊的左界和右界，也就是$height$陣列中連續高度$\geq \left|phone[k]\right|$的區間

時間複雜度：$O((\sum_{i=1}^{N}\left|phone[i]\right|)\log(\sum_{i=1}^{N}\left|phone[i]\right|)+Q\log(\sum_{i=1}^{N}\left|phone[i]\right|))$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
struct SuffixArray
{
    int S[400000],R[400000],H[400000];
    void BuildSa(const char *str,const int n)
    {
        static int tmp[3][400000];
        int *x=tmp[0],*y=tmp[1],*c=tmp[2],p=256;
        for(int i=0;i<p;i++)c[i]=0;
        for(int i=0;i<n;i++)c[x[i]=str[i]]++;
        for(int i=1;i<p;i++)c[i]+=c[i-1];
        for(int i=n-1;i>=0;i--)S[--c[x[i]]]=i;
        for(int move=1;move<n;move<<=1)
        {
            int cur=0;
            for(int i=n-move;i<n;i++)y[cur++]=i;
            for(int i=0;i<n;i++)if(S[i]>=move)y[cur++]=S[i]-move;
            for(int i=0;i<p;i++)c[i]=0;
            for(int i=0;i<n;i++)c[x[i]]++;
            for(int i=1;i<p;i++)c[i]+=c[i-1];
            for(int i=n-1;i>=0;i--)S[--c[x[y[i]]]]=y[i];
            swap(x,y);
            p=0,x[S[0]]=p++;
            for(int i=1;i<n;i++)
            {
                if(y[S[i]]!=y[S[i-1]]||(S[i]+move<n)!=(S[i-1]+move<n))x[S[i]]=p++;
                else assert(S[i]+move<n&&S[i-1]+move<n),x[S[i]]=(y[S[i]+move]==y[S[i-1]+move]?p-1:p++);
            }
            if(p==n)break;
        }
    }
    void BuildHeight(const char *str,const int n)
    {
        for(int i=0;i<n;i++)R[S[i]]=i;
        for(int i=0,ans=0;i<n;i++)
        {
            if(ans)ans--;
            if(R[i]==0){H[0]=0;continue;}
            const int j=S[R[i]-1];
            while(str[i+ans]==str[j+ans])ans++;
            H[R[i]]=ans;
        }
    }
    void Build(const char *str,const int len)
    {
        BuildSa(str,len);
        BuildHeight(str,len);
    }
}SA;
struct DisjointSets
{
    int S[400000];
    void Clear(const int N){for(int i=0;i<N;i++)S[i]=i;}
    int Find(const int a){return S[a]==a?a:(S[a]=Find(S[a]));}
    bool Merge(int a,int b)
    {
        if((a=Find(a))==(b=Find(b)))return false;
        S[a]=b;return true;
    }
};
struct QueryType
{
    int l,r,max_rank,ans;
}QUERY[1000000];
struct Bit
{
    int S[400001],N;
    void Clear(const int _N){N=_N;for(int i=1;i<=N;i++)S[i]=0;}
    void Add(int i){i++;for(;i<=N;i+=(i&(-i)))S[i]++;}
    int Query(int i){i++;int ans=0;for(;i;i-=(i&(-i)))ans+=S[i];return ans;}
};
int LENGTH;
void AnswerQueries(const int querycount)
{
    vector<int>order;
    for(int i=0;i<querycount;i++)order.push_back(i);
    sort(order.begin(),order.end(),[](const int a,const int b)->bool{return QUERY[a].max_rank<QUERY[b].max_rank;});
    static Bit bit;bit.Clear(LENGTH);
    int max_rank=0;
    for(const int qi:order)
    {
        QueryType &q=QUERY[qi];
        for(;max_rank<LENGTH&&max_rank<=q.max_rank;max_rank++)bit.Add(SA.S[max_rank]);
        q.ans=bit.Query(q.r)-bit.Query(q.l-1);
    }
}
int N;
vector<int>LOCS;
pair<int,int>SEGS[200000];
void BuildWordHeightSegments()
{
    vector<int>sortedword,sortedheight;
    vector<pair<int,int> >sorting;
    for(int i=0;i<N;i++)sorting.push_back(make_pair(-(LOCS[i+1]-LOCS[i]),i));
    sort(sorting.begin(),sorting.end());
    for(const auto &p:sorting)sortedword.push_back(p.second);
    sorting.clear();
    for(int i=1;i<LENGTH;i++)sorting.push_back(make_pair(-SA.H[i],i));
    sort(sorting.begin(),sorting.end());
    for(const auto &p:sorting)sortedheight.push_back(p.second);
    vector<pair<int,int> >().swap(sorting);
    auto sw=sortedword.begin(),sh=sortedheight.begin();
    static DisjointSets djl,djr;
    djl.Clear(LENGTH),djr.Clear(LENGTH);
    assert((int)sortedword.size()==N&&(int)sortedheight.size()==LENGTH-1);
    for(;sw!=sortedword.end();sw++)
    {
        for(;sh!=sortedheight.end()&&SA.H[*sh]>=LOCS[(*sw)+1]-LOCS[*sw]-1;sh++)
        {
            djl.Merge(*sh,(*sh)-1),djr.Merge((*sh)-1,*sh);
        }
        SEGS[*sw]=make_pair(djl.Find(SA.R[LOCS[*sw]+1]),djr.Find(SA.R[LOCS[*sw]+1]));
    }
    vector<int>().swap(sortedword);
    vector<int>().swap(sortedheight);
}
int Q;
char S[400000];
int main()
{
//    BuildSa("aabaaaab",8,SA),BuildHeight("aabaaaab",8,SA,RANK,HEIGHT);
//    for(int i=0;i<8;i++)printf("%d ",HEIGHT[i]);return 0;
//    freopen("in.txt","r",stdin);
    scanf("%d%d",&N,&Q);
    LOCS.push_back(-1);
    for(int i=0,&len=LENGTH=-1;i<N;i++)
    {
        len++;
        scanf("%s",S+len);
        while(S[len])len++;
        LOCS.push_back(len);
    }
    SA.Build(S,LENGTH);
    BuildWordHeightSegments();
    for(int i=0,l,r,k;i<Q;i++)
    {
        scanf("%d%d%d",&l,&r,&k);
        QUERY[i*2].l=QUERY[i*2+1].l=LOCS[l-1]+1;
        QUERY[i*2].r=QUERY[i*2+1].r=LOCS[r]-1;
        QUERY[i*2].max_rank=SEGS[k-1].first-1;
        QUERY[i*2+1].max_rank=SEGS[k-1].second;
    }
    AnswerQueries(Q*2);
    for(int i=0;i<Q;i++)printf("%d\n",QUERY[i*2+1].ans-QUERY[i*2].ans);
    return 0;
}