CF666E Forensic Examination

调了好久。。。

传送门

对所有的T串建出广义SAM，把询问离线下来按pr排序在S中跑匹配。那么子串$[pl,pr]$会在SAM中匹配到子串$[1,pr]$的节点。按$parent$树的定义，如果SAM中有子串$[pl,pr]$，它会属于当前节点的一个祖先$fa$，满足$len[fa]>=pr-pl+1$且深度最小。所以我们可以倍增找到$fa$。

现在我们知道每个询问所对应的节点了，需要知道他在每个串中的出现次数。

那么每个节点开一棵线段树，维护它出现最多的的串和出现次数，一开始只有叶子的线段树有值，所以要把叶子的线段树合并到父亲。

以及超级多的细节，比如说我现在又不知道为什么按串长从大到小合并到父亲会WA。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct SAM{
    int ch[26],fa,len;
}t1[100001];
struct sgt{
    int ch[2],size,maxn;
}t2[100001*40];
struct que{
    int pl,pr,l,r,h;
}q[500001];
struct edge{
    int next,to;
}w[100001];
struct node{int size,maxn;}ans[500001],e;
int n,tot_s=1,root[100001],fa[100001][19],last,now;
int m,tot_t,head[100001],cnt;
char ch[50001],s[500001];
inline bool cmp(que c,que d){return c.pr<d.pr;}
inline void add(int x,int y){
    w[++cnt].next=head[x];
    w[cnt].to=y; head[x]=cnt;
}
inline void pushup(int x){
    if (t2[t2[x].ch[0]].size>=t2[t2[x].ch[1]].size)
        t2[x].size=t2[t2[x].ch[0]].size,t2[x].maxn=t2[t2[x].ch[0]].maxn;
    else t2[x].size=t2[t2[x].ch[1]].size,t2[x].maxn=t2[t2[x].ch[1]].maxn;
}
int update(int rt,int l,int r,int x){
    if (!rt) rt=++tot_t;
    if (l==r){
        t2[rt].size++; t2[rt].maxn=x;
        return rt;
    }
    int mid=(l+r)>>1;
    if (x<=mid) t2[rt].ch[0]=update(t2[rt].ch[0],l,mid,x);
    else t2[rt].ch[1]=update(t2[rt].ch[1],mid+1,r,x);
    pushup(rt);
    return rt;
}
int merge(int c,int d,int l,int r){
    if (!c||!d) return c|d;
    int u=++tot_t;
    if (l==r){
        t2[u]=t2[c];
        t2[u].size+=t2[d].size;
        return u;
    }
    int mid=(l+r)>>1;
    t2[u].ch[0]=merge(t2[c].ch[0],t2[d].ch[0],l,mid);
    t2[u].ch[1]=merge(t2[c].ch[1],t2[d].ch[1],mid+1,r);
    pushup(u); return u;
}
node query(int rt,int l,int r,int x,int y){
    if (!rt) return e;
    node v=e,u=e;
    if (x<=l&&r<=y){
        v.size=t2[rt].size,v.maxn=t2[rt].maxn;
        return v;
    }
    int mid=(l+r)>>1;
    if (x<=mid) v=query(t2[rt].ch[0],l,mid,x,y);
    if (y>mid) u=query(t2[rt].ch[1],mid+1,r,x,y);
    if (u.size<=v.size) return v;
    return u;
}
void dfs(int x){
    for (int i=head[x]; i; i=w[i].next){
        fa[w[i].to][0]=x; dfs(w[i].to);
        root[x]=merge(root[x],root[w[i].to],1,n);
    }
}
inline void extend(int x){
    int np=++tot_s,p=last;
    last=np; root[np]=update(root[np],1,n,now);
    t1[np].len=t1[p].len+1;
    while (p&&!t1[p].ch[x]) t1[p].ch[x]=np,p=t1[p].fa;
    if (!p) t1[np].fa=1;
    else{
        int q=t1[p].ch[x];
        if (t1[q].len==t1[p].len+1) t1[np].fa=q;
        else{
            int cp=++tot_s; t1[cp]=t1[q];
            t1[cp].len=t1[p].len+1; t1[q].fa=t1[np].fa=cp;
            while (p&&t1[p].ch[x]==q) t1[p].ch[x]=cp,p=t1[p].fa;
        }
    }
}
int main(){
    int len;
    scanf("%s",s+1); scanf("%d",&n);
    for (int i=1; i<=n; i++){
        scanf("%s",ch+1);
        len=strlen(ch+1); last=1,now=i;
        for (int j=1; j<=len; j++) extend(ch[j]-'a');
    }
    for (int i=1; i<=tot_s; i++) add(t1[i].fa,i);
    dfs(1);
    for (int i=1; i<=18; i++)
        for (int j=1; j<=tot_s; j++)
            fa[j][i]=fa[fa[j][i-1]][i-1];
    scanf("%d",&m);
    for (int i=1; i<=m; i++)
        scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].pl,&q[i].pr),q[i].h=i;
    sort(q+1,q+m+1,cmp);
    int k=0,l=0,jp,u=1;
    for (int i=1; i<=m; i++){
        while (k<q[i].pr){
            k++;
            if (t1[u].ch[s[k]-'a']) u=t1[u].ch[s[k]-'a'],l++;
            else{
                while (u&&!t1[u].ch[s[k]-'a']) u=t1[u].fa,l--;
                if (!u) u=1,l=0;
                else l=t1[u].len+1,u=t1[u].ch[s[k]-'a'];
            }
        }
        if (l<q[i].pr-q[i].pl+1){ans[q[i].h].maxn=q[i].l; continue;}
        jp=u;
        for (int j=18; j>=0; j--)
            if (t1[fa[jp][j]].len>=q[i].pr-q[i].pl+1)
                jp=fa[jp][j];
        ans[q[i].h]=query(root[jp],1,n,q[i].l,q[i].r);
        if (!ans[q[i].h].size) ans[q[i].h].maxn=q[i].l;
    }
    for (int i=1; i<=m; i++) printf("%d %d\n",ans[i].maxn,ans[i].size);
    return 0;
}