题解 P4384 【[八省联考2018]制胡窜】

· · 题解

从去年九省联考咕咕咕到现在的一道题

细节相当烦人并且码量巨大，做好码4~5个kb的心理准备

前置芝士:后缀自动机(SAM)

如果你不知道什么是后缀自动姬或者知道后缀自动姬是什么但是想学的人

可以出门左转你站模板区包教包会

讲个笑话，SAM很休闲的

前置芝士:线段树合并

如果你不知道什么是线段树合并的话尽管你站没有他的膜板不过例题还是有几道，可以去看看这个博客然后做做里面的例题大概就可以get到这是一种怎样的算法了

讲个笑话，线段树合并挺休闲的

前置芝士:树上倍增

蛤？敢淦九省联考题不会树上倍增？你可以暂时不用看这篇题解了

本题题解

一句话题解:SAM倍增线段树合并三连，然后分情况讨论一下就做完了

当然这样写题解的人就该打死,我们还是好好讲下这题该怎么做

那么我们来复述一下并不明确的题意

给定一个字符串，每次询问一个子串(l,r)问你有多少中把这个字符串切成三段的方式使得每一段当中都含有一个和(l,r)这个子串一样的串

正难则反

那么显然直接做不是非常好做那么我们正难♂则反一下，我们用{n-1 \choose 2}(所有可能的切割方案)减去将这个字符串切成三段，每一段都不出现和(l,r)这个子串一样的串的方案数

那么我们假设(l,r)这个串在原串当中的一些位置(lx,rx)出现了,我们将所有出现位置的右端点构成的集合记为Right假设我们通过某种奥妙重重的手段get到了(l,r)这个区间的Right集合,那么让我们来看一看如何统计将这个字符串切成三段并且每段都不出现(l,r)的方案数

以下我们将和(l,r)这段子串长的一样的字符串称之为目标串

case1:出现了三个互不相交的目标串

根据抽屉原理你此时的方案数目肯定是0,因为你无论切到那两个字符串上第三个字符串总会被剩下

case2:没有出现三个互不相交的目标串

这种情况下我们的方案数目可能不是0了.那么我们依然需要继续分情况讨论

我们令leftpos表示right集合中的最小值(换句话说就是最靠左的右端点),ed表示最靠右的左端点(换句话说ed等于right集合当中的最大值减去询问串的长度+1)

case2.1:最靠左的目标串和最靠右的目标串是相交的

根据这个条件我们可以立即推出一个重要的事实是,所有目标串彼此是相交的,没有两个串互相分离

那这个性质有什么用呢？

我们可以将方案分成两类来进行统计

case2.1.1第一刀没有切完全部的目标串

那么我们依然会发现三个重要的性质可以帮助我们加速统计

第一，当第一刀固定在i这个位置的时候，合法的第二刀位置j的取值范围是一段连续的区间

这个性质相当好证明，第二刀必须切完剩下的所有目标串，显然只有切在剩下的线段的交集上才能切完,线段的交必然还是一段连续的线段,所以j的取值范围就是一段连续的区间

第二,如果第一刀切在p上，第二刀切在q上，那么p和q切掉的线段集合相同时p和q对应的合法的第二刀区间相同

切完之后剩下的线段相同同自然剩下的线段的交集也是相同的

第三,第二刀取值范围相同的第一刀位置也构成了一个连续的区间

由于所有线段的长度都是一样的，因此我们第一刀的位置在从左向右挪动的过程中每经过一个串才会多切一个线段，而在切完第i个串到切第i+1个串之间的区间所切的线段集合是不变的，自然第二刀的取值范围也相同

那么有了这些性质我们能干什么呢？

我们可以枚举第一刀的位置，并且将所有第二刀限制相同的第一刀位置用乘法分配律合并起来

换句话说,我们的式子就是这个，其中rt_{i}表示从左数第i个目标串的右端点

\sum_{i}((rt_{i+1}-len+1)-(rt_{i}-len+1))(rt_{i+1}-ed)

解释一下上面的式子就是第一刀在(rt_{i+1}-len+1,rt_{i}-len+1)的时候,第二刀的取值范围都是(ed,rt_{i+1})(因为rt_{i+1}是剩下的线段的右端点最小值,而ed是左端点的最大值)

所以两个区间长度直接乘起来就好了

简单化简一下式子就是

\sum_{i}(rt_{i+1}-r_{i})rt_{i+1}-ed\sum_{i}rt_{i+1}-rt_{i}

case2.1.2 其中一刀切完了全部的字符串

那么显然其中必然有一刀落在了(ed,leftpos)这个区间里，那么我们假如两刀都落在了这个区间当中，我们的方案数就是{leftpos-ed \choose 2}

接下来为了避免和上面的式子算重,我们考虑一下另一刀还可以放在哪里，我们发现刚才的式子当中已经统计好了第一刀落在(leftpos-len+1,leftpos)这个区间的方案数目了

所以我们现在有一刀落在了(ed,leftpos)这个区间，因此另一刀可能的取值范围就是(1,leftpos-len)和(leftpos+1,n)这两个区间

推一下式子就是

{leftpos-ed \choose 2}+(leftpos-ed)(n-len)

所以我们最靠左和最靠右的目标串是相交的这个情况就是这个式子了

\sum_{i}(rt_{i+1}-r_{i})rt_{i+1}-ed\sum_{i}rt_{i+1}-rt_{i}+{leftpos-ed \choose 2}+(leftpos-ed)(n-len)

case2.2 最靠左的目标串和最靠右的目标串并不相交

这种情况下由于我们知道并没有出现三个不相交的目标串，所以我们所有目标串就可以被分为三类

1.仅和最靠左的目标串相交

2.仅和最靠有的目标串相交

3.和两个串都相交

套用上一种情况的分析方式我们可以得出这个式子

\sum_{i}((rt_{i+1}-len+1)-(rt_{i}-len+1))(rt_{i+1}-ed)

但是和上一个情况不同的是这里需要加一点限制条件

rt_{i+1}>ed,rt_{i+1}+len-1<leftpos

另外一点需要注意的是这是对rt_{i+1}的限制，所以rt_{1}<ed并且应该是ed在right集合里的前驱

此时我们发现我们基本上计数完所有的方案了，但是我们还需要加上一点修正，就是上面的式子少统计了一种情况,也就是当我们的第一刀不断移动的时候,会在最后碰到leftpos而不是某一个串的左端点结束(在上一种情况当中不会出现这种情况,因为最后一个碰到的串的左端点是最右端的串,而后面的情况会一次性切断所有的串)

那么我们需要稍稍修正一下我们的式子，那就是我们查找一下leftpos+len-1在right集合中的前驱pre和后继suc，那么我们发现我们需要计算的情况就是第一刀的位置落在了(pre-len+1,leftpos)这个区间时的情况，那么我们发现此时第二刀的限制范围应该是(ed,suc)这个区间(因为右端点的最小值就是suc)

所以我们的式子就是这个式子(方括号用来规避非法情况)

(leftpos-pre+len+1)(suc-ed)[suc>ed]

然后把两种情况加起来就好了

维护right集合

前面的一系列推导都是基于我们可以通过某种奥妙重重的方式来get到right集合才能实现的,那么问题来了我们该如何维护right集合呢？

如果你对后缀自动姬那一套理论相当熟悉的话你会知道一个串的right集合就是这个串在后缀自动姬对应节点的right集合

那么我们想要知道一个后缀自动姬节点的right集合长什么样我们是没有办法直接知道的，我们知道这个点的right集合等于他在parent树的子树中所有点的right集合的并集

因此我们可以通过合并这个节点的孩子们的right集合来求出这个点的right集合了，这个东西在parent树上跑一个线段树合并就出来了

具体实现的时候对于后缀自动姬中每一个代表前缀缀i的节点我们把i这个元素插入到权值线段树中去，接下来在树上dfs，将这个点的孩子全部合并起来就是这个点的right集合了

那么问题来了我们如何定位一个子串在后缀自动姬上对应的节点位置呢？

一个相当暴力的想法是直接在后缀自动姬上大力跑这个子串可以确定这个子串的位置

不过另一种方式是通过树上倍增的方式不断的从parent树上表示前缀r的节点向上跳，一直保证对应节点的len值不小于我们这个子串的长度，这样倍增下去我们就可以快速的定位了

定位了之后我们就可以把这个询问挂到这个节点上了，最后在parent树上dfs一下就可以回答每一个询问了

线段树合并的时候为了回答每一询问我们需要维护的信息是

\sum_{i}(rt_{i+1}-rt_{i})rt_{i+1} \sum_{i}(rt_{i+1}-rt_{i})

这个东西维护的方式也相当简单，我们线段树上每一个节点维护一下最大值和最小值，然后我们就可以愉快的合并两个节点的信息了也就可以维护了

同理我们也可以利用维护的最大值和最小值的信息快速的查询前驱和后继

复杂度O((n+q)logn)细节基本分情况讨论完了，关于实现时候的一些trick可以自行参考代码

上代码~

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;const int N=1e5+10;typedef long long ll;
int n;int m;int v[2*N];int x[2*N];int al[2*N];int ct;char mde[N];
int len[2*N];ll ans[3*N];int fa[2*N][22];//倍增 
struct qry{int len;int tim;};vector <qry> vq[2*N];
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline void dfs1(int u)//预处理倍增数组 
{
    for(int i=0;fa[u][i];i++)fa[u][i+1]=fa[fa[u][i]][i];
    for(int i=al[u];i;i=x[i])fa[v[i]][0]=u,dfs1(v[i]);
}
inline int ck(int p,int le)//倍增定位 
{for(int i=20;i>=0;i--)if(fa[p][i]&&len[fa[p][i]]>=le)p=fa[p][i];return p;}
inline ll ctwo(ll p){return (p*(p-1))>>1;}
struct suffixautomaton//简易后缀自动姬膜板 
{
    int mp[2*N][10];int fa[2*N];int ct;
    inline void ih(){for(int i=1;i<=n;i++)len[i]=i;ct=n+1;}
    inline void ins(int i,int c)
    {
        int p=(i-1)?(i-1):(n+1);
        for(;p&&mp[p][c]==0;p=fa[p])mp[p][c]=i;
        if(!p){fa[i]=n+1;return;}int q=mp[p][c];
        if(len[q]==len[p]+1){fa[i]=q;return;}
        ++ct;len[ct]=len[p]+1;
        for(int i=0;i<=9;i++)mp[ct][i]=mp[q][i];
        for(;p&&mp[p][c]==q;p=fa[p])mp[p][c]=ct;
        fa[ct]=fa[q];fa[q]=ct;fa[i]=ct;
    }
    inline void build(){for(int i=1;i<=ct;i++)add(fa[i],i);}
}sam;
struct linetree//线段树合并板子 
{
    int mi[22*N];int mx[22*N];ll v1[22*N];ll v2[22*N];
    int s[22*N][2];int rt;ll ans1;ll ans2;int ct;
    inline void mg(const int& p)//合并这个节点的两个孩子 
    {
        int ls=s[p][0];int rs=s[p][1];
        if(!rs){mi[p]=mi[ls];mx[p]=mx[ls];v1[p]=v1[ls];v2[p]=v2[ls];return;}
        if(!ls){mi[p]=mi[rs];mx[p]=mx[rs];v1[p]=v1[rs];v2[p]=v2[rs];return;}
        mi[p]=mi[ls];mx[p]=mx[rs];ll del=mi[rs]-mx[ls];
        v1[p]=v1[ls]+v1[rs]+del*mi[rs];v2[p]=v2[ls]+v2[rs]+del;
    }
    inline void mg(int p1,int p2)//线段树合并 
    {
        if(s[p1][0]&&s[p2][0])mg(s[p1][0],s[p2][0]);else if(s[p2][0])s[p1][0]=s[p2][0];
        if(s[p1][1]&&s[p2][1])mg(s[p1][1],s[p2][1]);else if(s[p2][1])s[p1][1]=s[p2][1];mg(p1);
    }
    inline void ins(int p,int l,int r,int pos//插入一个节点
    {
        mi[p]=mx[p]=pos;if(r-l==1){return;}int mid=(l+r)/2;
        if(pos<=mid)ins(s[p][0]=++ct,l,mid,pos);
        else ins(s[p][1]=++ct,mid,r,pos);
    }
    inline int qmi(int p,int l,int r,int dl,int dr)//区间最小值 
    {
        if(dl==l&&dr==r){return mi[p];}int mid=(l+r)/2;ll res=0x3f3f3f3f;
        if(dl<mid&&s[p][0])res=qmi(s[p][0],l,mid,dl,min(dr,mid));
        if(res!=0x3f3f3f3f)return res;
        if(mid<dr&&s[p][1])return qmi(s[p][1],mid,r,max(dl,mid),dr);return 0x3f3f3f3f;
    }
    inline int qmx(int p,int l,int r,int dl,int dr)//区间最大值 
    {
        if(dl==l&&dr==r){return mx[p];}int mid=(l+r)/2;ll res=-0x3f3f3f3f;
        if(mid<dr&&s[p][1])res=qmx(s[p][1],mid,r,max(dl,mid),dr);
        if(res!=-0x3f3f3f3f)return res;
        if(dl<mid&&s[p][0])return qmx(s[p][0],l,mid,dl,min(dr,mid));return -0x3f3f3f3f;
    }
    inline void qry(int p,int l,int r,int dl,int dr)//询问的时候新开一个节点从左到右合并 
    {
        if(dl==l&&dr==r)
        {
            if(rt==-1){rt=mx[p];ans1=v1[p];ans2=v2[p];return;}
            else {ll del=mi[p]-rt;rt=mx[p];ans1+=v1[p]+mi[p]*del;ans2+=v2[p]+del;return;}
        }int mid=(l+r)/2;
        if(dl<mid&&s[p][0])qry(s[p][0],l,mid,dl,min(dr,mid));
        if(mid<dr&&s[p][1])qry(s[p][1],mid,r,max(dl,mid),dr);
    }
    inline ll cqry(int u,int l,int r,int st,int ed)
    {if(l>r)return 0;rt=st;ans1=0;ans2=0;qry(u,0,n,l-1,r);return ans1-ed*ans2;}
    inline ll calc(int p,int ed){return v1[p]-ed*v2[p];}
}lt;
inline void dfs2(int u)
{
    for(int i=al[u];i;i=x[i])dfs2(v[i]),lt.mg(u,v[i]);
    int lp=lt.mi[u];int rp=lt.mx[u];vector <qry> :: iterator  it;
    for(it=vq[u].begin();it!=vq[u].end();++it)
    {
        int ed=rp-it->len+1;//情况1 
        if(ed<=lp){ans[it->tim]+=lt.calc(u,ed)+ctwo(lp-ed)+(ll)(lp-ed)*(n-it->len);}
        else 
        {
            int pos=lt.qmx(u,0,n,0,ed);if(pos-it->len+1>=lp)continue;//判断3个字符串是否不相交可以查max来解决 
            ans[it->tim]+=lt.cqry(u,ed+1,lp+it->len-1,pos,ed);//这里传参数的时候直接把开头传进去了 
            int pos1=lt.qmi(u,0,n,lp+it->len-1,n);pos=lt.qmx(u,0,n,0,lp+it->len-1);
            if(pos!=-0x3f3f3f3f&&pos1!=0x3f3f3f3f)//修正 
                ans[it->tim]+=(lp-pos+it->len-1)*(pos1-ed)*(pos1>=ed);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);scanf("%s",mde+1);sam.ih();
    for(int i=1;i<=n;i++)sam.ins(i,mde[i]-'0');
    lt.ct=sam.ct;sam.build();dfs1(n+1);
    for(int i=1,l,r;i<=m;i++)//离线 
        scanf("%d%d",&l,&r),vq[ck(r,r-l+1)].push_back((qry){r-l+1,i});
    for(int i=1;i<=n;i++)lt.ins(i,0,n,i);dfs2(n+1);
    for(int i=1;i<=m;i++)printf("%lld\n",ctwo(n-1)-ans[i]);return 0;//拜拜程序 
}