题解 CF666E 【Forensic Examination】

xtx1092515503 · 2020-08-07 09:18:37 · 题解

CF666E Forensic Examination

这里是一种后缀数组+莫队的奇妙解法~~~

首先，常规套路就是将所有串中间插上一个字符然后并一起跑后缀排序。这样跑完之后我们发现，如果我们要求英文题面中“禁忌串”中一段子串 [p_l,p_r] 的出现位置，就可以等价于所有后缀 i，使得 \operatorname{LCP}(i,p_l)\geq p_r-p_l+1。依据 \text{LCP Lemma}，这是后缀数组中，rk_{p_l} 左右两侧的一段区间。于是我们建出ST表，在后缀数组上二分就能找出这段区间。

这样搞完之后，我们发现问题就被转化为：在后缀数组中的一段区间里，来自哪本英文题面中“小册子”的后缀是出现最多的？

显然这是一个区间众数问题，常规解法是分块（这题）或者莫队。但是因为这题并没有强制在线，并且对众数的值域是有限制的（只有来自 [l,r] 区间里的小册子才会被考虑），我们只能考虑莫队。

因为对值域有要求，我们考虑再关于值域分块。对于每个块，我们需要记录块内出现次数最多的那本小册子出现了多少次。显然当莫队往区间里加入元素时很好处理，直接取 \max 即可。但是如果要删除元素呢？

显然删除一个元素时，众数出现次数最多减一。于是我们可以针对每个块开一个桶，记录块中有多少元素的出现次数为 i。当一次删除后，如果我们发现众数次数对应的那个桶已经空了，就令众数减一即可。

然后最终统计答案时，就是一个常规的分块，整块直接调用块中众数，散块暴力扫过即可。

我们下面来分析复杂度。按照我们代码中的写法，我们设 n 表示所有串并一起的长度，A 表示小册子的数量，m 表示询问数。显然，应用我们刚才的方法，莫队单次端点移动是 O(1) 的，莫队统计一次答案是 O(\sqrt{A}) 的。它一共最多移动 m\sqrt{n} 次端点，统计 m 次答案，故该部分复杂度为 O\Big(m(\sqrt{n}+\sqrt{A})\Big)。然后算上后缀数组的 O(n\log n) 倍增排序与ST表，以及 m\log n 的二分，因此总复杂度为 O\Big((m+n)\log n+m(\sqrt{n}+\sqrt{A})\Big)。

然后是空间部分。我们有ST表的 n\log n 和桶的大小。因为我们对于每个块都开了一个桶，所以桶的大小是 O(A\sqrt{A}) 的。但是因为 A 很小（5\times 10^4），所以开的下。

如果你是空间大小的狂热追求者的话，我们还有一种优化至 O(A) 的方法，即因为众数个数变化幅度一次只有 \pm1，因此我们可以使用 std::vector<int> 来维护桶，每次在结尾 pop 或 push 即可。因为所有“小册子”的总长只有 5\times10^4，所以该方法空间消耗即为 5\times 10^4，即 O(A)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=600100;
int A,B,id[N];
struct Node{
    int id,val;
    Node(int x=0x3f3f3f3f,int y=0){id=x,val=y;}
    friend bool operator <(const Node &x,const Node &y){
        return x.val!=y.val?x.val<y.val:x.id>y.id;
    }
}res[N];
namespace Suffix_Array{
    int x[N],y[N],buc[N],sa[N],ht[N],rk[N],s[N],n,m,LG[N],mn[N][20];
    char str[N];
    bool mat(int a,int b,int k){
        if(y[a]!=y[b])return false;
        if((a+k<n)^(b+k<n))return false;
        if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
        return true;
    }
    void SA(){
        for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
        for(int k=1;k<n;k<<=1){
            int num=0;
            for(int i=n-k;i<n;i++)y[num++]=i;
            for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
            for(int i=0;i<=m;i++)buc[i]=0;
            for(int i=0;i<n;i++)buc[x[y[i]]]++;
            for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
            for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
            swap(x,y);
            x[sa[0]]=num=0;
            for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
            if(num>=n-1)break;
            m=num;
        }
        for(int i=0;i<n;i++)rk[sa[i]]=i;
        for(int i=0,k=0;i<n;i++){
            if(!rk[i])continue;
            if(k)k--;
            int j=sa[rk[i]-1];
            while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
            ht[rk[i]]=k;
        }
        for(int i=2;i<N;i++)LG[i]=LG[i>>1]+1;
        for(int i=1;i<N;i++)mn[i][0]=ht[i];
        for(int j=1;j<=LG[N-1];j++)for(int i=1;i+(1<<j)-1<N;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
    }
    int LCP(int x,int y){
        if(x>y)swap(x,y);
        x++;
        int k=LG[y-x+1];
        return min(mn[x][k],mn[y-(1<<k)+1][k]);
    }
    void Range(int x,int k,int &L,int &R){
        int l,r;
        x=rk[x];
        l=0,r=x;
        while(l<r){
            int mid=(l+r)>>1;
            if(LCP(mid,x)>=k)r=mid;
            else l=mid+1;
        }
        L=r;
        l=x,r=n-1;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(LCP(mid,x)>=k)l=mid;
            else r=mid-1;
        }
        R=l;
    }
}
using namespace Suffix_Array;
const int BBB=800;
const int CCC=300;
int BLK[50100],lp[50100];
struct Query{
    int l,r,ql,qr,id;
    friend bool operator <(const Query &x,const Query &y){
        if(x.r/BBB!=y.r/BBB)return x.r<y.r;
        return (x.r/BBB)&1?x.l<y.l:x.l>y.l;
    }
}q[500100];
int cnt[50100],occ[200][50100],lim[200];
void Push(int x){
    x=id[sa[x]];
    if(x==-1)return;
    occ[BLK[x]][cnt[x]]--;
    cnt[x]++;
    occ[BLK[x]][cnt[x]]++;
    lim[BLK[x]]=max(lim[BLK[x]],cnt[x]);
}
void Pop(int x){
    x=id[sa[x]];
    if(x==-1)return;
    occ[BLK[x]][cnt[x]]--;
    cnt[x]--;
    occ[BLK[x]][cnt[x]]++;
    if(!occ[BLK[x]][lim[BLK[x]]])lim[BLK[x]]--;
}
void Ask(int l,int r,Node &ans){
    r++;
    if(BLK[l]==BLK[r]){for(int i=l;i<r;i++)ans=max(ans,Node(i,cnt[i]));return;}
    int pos=BLK[A];
    for(int i=BLK[l]+1;i<BLK[r];i++)if(lim[i]>lim[pos])pos=i;
    if(pos!=BLK[A])for(int i=lp[pos];i<lp[pos+1];i++)ans=max(ans,Node(i,cnt[i]));
    for(int i=l;i<lp[BLK[l]+1];i++)ans=max(ans,Node(i,cnt[i]));
    for(int i=lp[BLK[r]];i<r;i++)ans=max(ans,Node(i,cnt[i]));
}
int main(){
    scanf("%s",str),m=strlen(str);for(int i=0;i<m;i++)s[n]=str[i]-'a'+1,id[n]=-1,n++;
    scanf("%d",&A);
    for(int i=0;i<A;i++){
        s[n]=i+26,id[n]=-1,n++;
        scanf("%s",str),m=strlen(str);
        for(int j=0;j<m;j++)s[n]=str[j]-'a'+1,id[n]=i,n++;
    }
//  for(int i=0;i<n;i++)printf("%d ",s[i]);puts("");
    m=A+26;
    SA();
    scanf("%d",&m);
    for(int i=1,a,b,c,d;i<=m;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        Range(c-1,d-c+1,q[i].l,q[i].r);
        q[i].ql=a-1,q[i].qr=b-1;
        q[i].id=i;
    }
    for(int i=0;i<A;i++)BLK[i]=i/CCC;
    for(int i=0;i<=BLK[A-1];i++)lp[i]=i*CCC;
    BLK[A]=BLK[A-1]+1;
    lp[BLK[A]]=A;
    sort(q+1,q+m+1);
    Push(0);
    for(int i=1,L=0,R=0;i<=m;i++){
        while(L>q[i].l)Push(--L);
        while(R<q[i].r)Push(++R);
        while(L<q[i].l)Pop(L++);
        while(R>q[i].r)Pop(R--);
        Ask(q[i].ql,q[i].qr,res[q[i].id]);
    }
    for(int i=1;i<=m;i++)printf("%d %d\n",res[i].id+1,res[i].val);
    return 0;
}