题解 P5576 【[CmdOI2019]口头禅】

2018LZY · 2020-03-31 21:28:29 · 题解

更好的阅读体验

前言

毒瘤题 and 毒瘤出题人.

无限 orz~~ cmd.

前置知识

内存池小技巧:开一大块静态内存,然后用指针标记位置.

(避免用vector等常数巨大的STL).

猫树:本题运用了类似的思想,但是并没有用线段树.

(我称本题运用的方法为"猫树分治).

猫树分治的思想:

把区间询问,转化为以中间某个状态为中心的DP. 结合前缀/后缀最值,达到问题的要求.

正题

考虑暴力. 对于[l,r]区间,我们可以选择其中一个位置mid.

定义f[j]表示s[mid]的前缀j在s[l...r]的最长公共后缀.(子串一定是一个前缀的后缀)

对于其他所有位置i\ne mid,让s[mid]在SAM[i]上跑,假如已加入j个字符,成功匹配len个后缀,那么f[j]=min(f[j],len).

最后ans=\max_{i=1}^{|s[mid]|} f[i].

设len为总字符数,S=s[mid]. 复杂度为O((r-l+1)|S|+len). 显然,取较短的求得更快.

当然我们不可能每个询问都是这样处理,实际上我们先对f做以mid为中心的前后缀处理,然后用O(|S|)扫描数组合并答案.

根据上面的思想,我们先把长度小的用于求解.

我们采取倍增分治,每次把 \le 2^x 的串给 提取出来做贡献,之后x++.(这样的好处在于,每个询问产生贡献的S和最小串的很接近)

单次(一个x)每个串会被遍历O(\log n)次,总共有\log len个x.所以总共每个串会被遍历O(\log n\log len).

首先,分治预处理(求mid为中心的前后缀)的复杂度为O(len\log n\log len).

然后,设区间内跨mid的询问数有m个.

如果|S|\le \dfrac {len}{\sqrt m},那么扫描的复杂度即为O(|S|\sqrt m)=O(len\sqrt m). 否则,那么区间的长度k=r-l+1\le \sqrt m,本质不同的区间为k^2个,记忆化一下,总复杂度为O(k^2\cdot \dfrac{len}{k})=O(len\sqrt m).

总复杂度为O(len(\log n\log len+\sqrt m)+m\log m).

码风好评

#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define gc getchar()
#define cmin(x,y) ((x)>(y)?x=y:0)
using namespace std;
const int N=20010,M=1e5+10,S=800010;

void qr(int &x) {
    char c=gc; x=0;
    while(!isdigit(c))c=gc;
    while(isdigit(c))x=x*10+c-'0',c=gc;
}
void qw(int x) {
    if(x/10) qw(x/10);
    putchar(x%10+'0');
}
void pr(int x) {qw(x); puts("");}

struct node{int fa,len,v[2];}tr[S]; int tot;
struct SAM {
    int last,root;
    void add(int c) {
        register int p=last,x=last=++tot; tr[x].len=tr[p].len+1;
        for(    ;p&&!tr[p].v[c];p=tr[p].fa) tr[p].v[c]=x;
        if(!p) tr[x].fa=root;
        else {
            int q=tr[p].v[c],y;
            if(tr[p].len+1==tr[q].len) tr[x].fa=q;
            else {
                tr[y=++tot]=tr[q];
                tr[y].len=tr[p].len+1;
                tr[q].fa=tr[x].fa=y;
                for(    ;p&&tr[p].v[c]==q;p=tr[p].fa) tr[p].v[c]=y;
            }
        }
    }
    void bt(char *s) {
        last=root=++tot;
        for(int i=0;s[i];i++) 
            add(s[i]-'0');
    }
}t[N];

int n,m;
char _str[S],*str[N],*spos=_str; int len[N];
int _f[S],*f[N],*Fpos=_f;

//询问 
struct Q {
    int l,r,pos;
    bool operator <(Q b) const {
        return l^b.l?l<b.l:r<b.r;
    }
    bool operator ==(Q b) const {
        return l==b.l&&r==b.r;
    }
}q[M],lq[M],rq[M];
int ans[M];

int sta[N],top;

void solve(int l,int r,int L,int R,int lim) {//[l,r],[L,R]分别为串范围,询问范围 
    if(L>R) return ;
    do {
        top=0;
        for(int i=l;i<=r;i++) if(len[i]<=lim) sta[++top]=i;
        if(top) break;
        lim *= 2;
    } while(1);
    int mid=sta[top+1>>1];//取一个较小又在中间的数
    int tmp=len[mid];

    Fpos=_f;
    for(int i=l;i<=r;i++) f[i]=Fpos,Fpos+=tmp+1;//分配区间 
    for(int i=0;i<tmp;i++) f[mid][i]=i+1;//类似猫树思想进行处理

    for(int i=mid-1;i>=l;i--) {
        int p=t[i].root,cnt=0;//对应状态,匹配长度 
        for(int j=0;j<tmp;j++) {
            int c=str[mid][j]-'0';
            if(!tr[p].v[c]) {
                while(p!=t[i].root&&!tr[p].v[c]) 
                    p=tr[p].fa;
                cnt=tr[p].len;
            }
            if(tr[p].v[c]) p=tr[p].v[c],cnt++;
            f[i][j]=min(f[i+1][j],cnt);
            //f[i][j] 表示str[mid] 前缀j在[i,mid]这些串中的最长公共后缀. 
        }
    }

    for(int i=mid+1;i<=r;i++) {
        int p=t[i].root,cnt=0;
        for(int j=0;j<tmp;j++) {
            int c=str[mid][j]-'0';
            if(!tr[p].v[c]) {
                while(p!=t[i].root&&!tr[p].v[c]) 
                    p=tr[p].fa;
                cnt=tr[p].len;
            }
            if(tr[p].v[c]) p=tr[p].v[c],cnt++;
            f[i][j]=min(f[i-1][j],cnt);
        }
    }

    int lt=0,rt=0;
    for(int i=L;i<=R;i++) {
        int a=q[i].l,b=q[i].r;
        if(a<=mid&&mid<=b) {
            if(q[i]==q[i-1]) ans[q[i].pos]=ans[q[i-1].pos];
            else {
                int res=0;
                for(int j=0;j<tmp;j++)
                    res=max(res,min(f[a][j],f[b][j]));
                ans[q[i].pos]=res;
            }
        }
        else if(b<mid) lq[++lt]=q[i];
        else rq[++rt]=q[i];
    }

    Q *g=q+L-1;
    for(int i=1;i<=lt;i++) g[i]=lq[i];
    g+=lt;
    for(int i=1;i<=rt;i++) g[i]=rq[i];

    solve(l,mid-1,L,L+lt-1,lim);
    solve(mid+1,r,L+lt,L+lt+rt-1,lim);
}

int main() {
    qr(n); qr(m);
    for(int i=1;i<=n;i++) {
        scanf("%s",str[i]=spos);
        len[i]=strlen(str[i]);
        spos+=len[i];
        t[i].bt(str[i]);
    }
    for(int i=1;i<=m;i++)
        qr(q[i].l),qr(q[i].r),q[i].pos=i;
    sort(q+1,q+m+1);
    solve(1,n,1,m,10);
    for(int i=1;i<=m;i++) pr(ans[i]);
    return 0;
}