题解 P4094 【[HEOI2016/TJOI2016]字符串】

· · 题解

作为一道码农题……

(SA+二分套(主席树+二分))怕不是真·理论复杂度O(Nlog^2N)

如果熟练的压行的话应该可以做到百行以内吧

那么我们来讲解一下这道题：设我们的答案为mid(注意这里有坑是[a,b]的所有子串和[c,d]这个子串的最长lcp),那么我们会发现一个很有趣的事实: 如果mid可行的话，那么任意一个比mid小的数也可行

也就是说，问题满足可二分性，那么我们可以二分答案，将原问题转化为一个判定性问题:mid这个答案行不行？

那么我们发现，如果mid这个答案可以的话，就会存在一个后缀S，

1.它的开头在[a,b-mid+1]当中。

2.lcp(S,c)>=mid。

再次转化一步，就是询问满足以上两个条件的后缀S的个数，经典的二元限制统计问题，我们的思路很简单，摁死一个再去管下一个，发现一件有趣的事实：如果把这些后缀排好序，那么lcp符合要求的一定是一段连续的区间，(为什么？，因为我们发现排好序以后，lcp这个函数是单峰的，并且峰值在自己这里)

那么我们似乎可以二分左端点和右端点，为此我们需要O(1)求出区间最小值，为此我们还得写一个St表QAQ

那么最后我们发现现在两个限制都是区间型的了，而且是静态区间，没有修改，所以可以用主席树查询一发……

下面是科普

只是介绍一些关于数据结构/算法的引申，并不会详细介绍原理，如果不会的话看对应的膜板吧，解释的都很详细

关于后缀数组

ht数组的意义是，lcp(rk[i-1],rk[i])，所以ht数组是在按sa序排出来之后才有意义的，另外我们会发现ht数组是“向上”匹配的，所以我们使用区间min来查询任意两个串的lcp时查询的是(rk[a],rk[b]]即左开右闭区间。

关于st表

考虑到ht数组向上匹配的特性，我们的区间min也写成左开右闭就好了

关于主席树

主席树其实是线段树的前缀和，我们的线段树通常是一个权值线段树以满足我们对权值的区间限制要求，那么我们建主席树的时候通常是一个点一个点插入，以满足每一个实际区间的要求，对于这道题来讲，我们对sa建主席树，因为最后实际上第二次二分的区间是一个在sa序上连续的区间，查询限制的则是这个后缀的实际编号，所以我们的权值线段树的权值是后缀的编号。

上代码~

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100010;int n;int m;
char mde[N];int sa[N];int rk[2*N];int ht[N];
int x[N];int y[N];queue <int> q[N];
inline bool cmp(int i,int j){return (x[i]==x[j])&&(y[i]==y[j]);}
inline void rixs()//这里的后缀数组用的是队列实现，常数较大
{
    for(int i=1;i<=n;i++){q[y[i]].push(i);}
    int cnt=0;for(int i=0;i<=n;i++)
    {for(;!q[i].empty();q[i].pop()){sa[++cnt]=q[i].front();}}
    for(int i=1;i<=n;i++){q[x[sa[i]]].push(sa[i]);}
    cnt=0;for(int i=0;i<=n;i++)
    {for(;!q[i].empty();q[i].pop()){sa[++cnt]=q[i].front();}}
    rk[sa[1]]=1;for(int i=2;i<=n;i++)
    {rk[sa[i]]=(cmp(sa[i-1],sa[i]))?rk[sa[i-1]]:i;}
}
inline void create_sa()//板子啥的问度娘吧
{
    for(int i=1;i<=n;i++){q[mde[i]-'a'+1].push(i);}
    int cnt=0;for(int i=1;i<=26;i++)
    {for(;!q[i].empty();q[i].pop()){sa[++cnt]=q[i].front();}}
    rk[sa[1]]=1;for(int i=2;i<=n;i++)
    {rk[sa[i]]=(mde[sa[i-1]]==mde[sa[i]])?rk[sa[i-1]]:i;}
    for(int k=1;k<=n;k*=2)
    {for(int i=1;i<=n;i++){x[i]=rk[i];y[i]=rk[i+k];}rixs();}
}
inline void calch()
{
    int j=0;int k=0;for(int i=1;i<=n;ht[rk[i++]]=k)
    {for(k=k?k-1:k,j=sa[rk[i]-1];mde[i+k]==mde[j+k];k++);}
}
int st[22][N];int log[N];
inline void calclog()//打表log，方便使用
{int i=0;for(int j=1;j<=n;j++){if((1<<(i+1))<=j)i++;log[j]=i;}}
inline void create_st()//对ht建st表
{
    for(int i=0;i<=n-1;i++){st[0][i]=ht[i+1];}
    for(int i=1;i<=log[n];i++)
    {for(int j=0;j<n-(1<<(i-1));j++){st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);}}
}
inline int rmq(int l,int r)//左开右闭的rmq
{int len=r-l;int res=min(st[log[len]][l],st[log[len]][r-(1<<log[len])]);return res;}
struct per_linetree//主席树的板子，这个真的是纯板子了
{
    int s[2][44*N];int fa[44*N];int root[N];int cnt;int val[44*N];
    per_linetree(){root[0]=1;cnt=1;}
    inline void insert(int p1,int p2,int l,int r,int pos)
    {
        val[p2]=val[p1]+1;if(r-l==1)return;int mid=(l+r)/2;
        if(pos<=mid){s[0][p2]=++cnt;s[1][p2]=s[1][p1];insert(s[0][p1],cnt,l,mid,pos);}
        else {s[1][p2]=++cnt;s[0][p2]=s[0][p1];insert(s[1][p1],cnt,mid,r,pos);}
    }
    inline void add(int t1,int t2,int pos)
    {root[t2]=++cnt;insert(root[t1],root[t2],0,n,pos);}
    inline int sum(int p1,int p2,int l,int r,int dl,int dr)
    {
        if(dl==l&&dr==r){return val[p2]-val[p1];}int mid=(l+r)/2;int res=0;
        if(dl<mid)res+=sum(s[0][p1],s[0][p2],l,mid,dl,min(dr,mid));
        if(mid<dr)res+=sum(s[1][p1],s[1][p2],mid,r,max(dl,mid),dr);
        return res;
    }
    inline int query(int t1,int t2,int l,int r)
    {return sum(root[t1-1],root[t2],0,n,l-1,r);}
}plt;
inline bool jud(int x,int a,int b,int c)//检测mid是否可行
{
    int l=1;int r=rk[c];int up;int down;//二分上边界，注意是左开右闭
    while(l<r){int mid=(l+r)/2;if(rmq(mid,rk[c])<x){l=mid+1;}else {r=mid;}}
    up=r;
    l=rk[c];r=n;//二分下边界
    while(l<r){int mid=(l+r+1)/2;if(rmq(rk[c],mid)<x){r=mid-1;} else{l=mid;}}
    down=r;
    return plt.query(up,down,a,b-x+1)!=0;//主席树查一发是否存在符合要求的后缀
}
inline int solve(int a,int b,int c,int d)//主二分过程
{
    int l=0;int r=min(b-a+1,d-c+1);//这个就是裸的二分答案了
    while(l<r){int mid=(l+r+1)/2;if(jud(mid,a,b,c)){l=mid;}else {r=mid-1;}}
    return r;
}
int main()
{
    scanf("%d%d",&n,&m);scanf("%s",mde+1);
    create_sa();calch();calclog();create_st();//上来先预处理
    for(int i=1;i<=n;i++){plt.add(i-1,i,sa[i]);}//对sa建主席树
    for(int i=1;i<=m;i++)
    {
        int a;int b;int c;int d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        printf("%d\n",solve(a,b,c,d));
    }return 0;//拜拜程序~
}