【CF666E】Forensic Examination
题意：给你一个字符串s和一个字符串集合$\{t_i\}$。有q个询问，每次给出$l,r,p_l,p_r$，问$s[p_l,p_r]$在$t_l...t_r$中的哪个字符串中出现的次数最多，以及最多次数是多少。
$|s|\le 5\times 10^5,\sum |t_i|\le 5\times 10^4,q\le 5\times10^5$
题解：我们对于$t_i$建立广义后缀自动机，并对于每个节点都维护：在它的right集合中，每个字符串出现的次数，以及区间出现次数最大值。这个用线段树合并很容易搞定。我们将询问离线并按右端点排序，对于询问$p_l,p_r$，我们已经将s的前$p_r$位放到广义后缀自动机里匹配得到了其对应的位置，现在我们只需不断沿着pre指针向上跳，找到最后一个长度$\ge p_r-p_l+1$的状态即可。这一步可以用倍增实现。既然我们已经找到了那个状态，我们直接在那个状态的线段树中查询一下$[l,r]$的最大值即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=100010;
const int maxm=500010;
int ch[maxn][26],pre[maxn],mx[maxn];
int n,m,tot,N,Q,cnt,last;
char S[maxm],T[maxn];
int to[maxn],nxt[maxn],head[maxn],rt[maxn],fa[18][maxn],Log[maxn];
int sl[maxm],sr[maxm],pl[maxm],pr[maxm];
vector<int> q1[maxm],q2[maxn];
vector<int>::iterator it;
struct node
{
int x,y;
node() {}
node(int a,int b) {x=a,y=b;}
bool operator < (const node &a) const {return (x==a.x)?(y>a.y):(x<a.x);}
}ans[maxm];
struct sag
{
int ls,rs;
node v;
}s[maxn*20];
void extend(int x)
{
int p=last;
if(ch[p][x])
{
int q=ch[p][x];
if(mx[q]==mx[p]+1) last=q;
else
{
int nq=++tot; last=nq;
mx[nq]=mx[p]+1,pre[nq]=pre[q],pre[q]=nq;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=nq;
}
}
else
{
int np=++tot;
last=np,mx[np]=mx[p]+1;
for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=np;
if(!p) pre[np]=1;
else
{
int q=ch[p][x];
if(mx[q]==mx[p]+1) pre[np]=q;
else
{
int nq=++tot;
mx[nq]=mx[p]+1,pre[nq]=pre[q],pre[q]=pre[np]=nq;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=nq;
}
}
}
}
inline void add(int a,int b)
{
to[cnt]=b,nxt[cnt]=head[a],head[a]=cnt++;
}
void insert(int l,int r,int &x,int a)
{
if(!x) x=++N;
if(l==r)
{
s[x].v.x++,s[x].v.y=l;
return ;
}
int mid=(l+r)>>1;
if(a<=mid) insert(l,mid,s[x].ls,a);
else insert(mid+1,r,s[x].rs,a);
s[x].v=max(s[s[x].ls].v,s[s[x].rs].v);
}
int merge(int x,int y)
{
if(!x||!y) return x^y;
if(!s[x].ls&&!s[x].rs)
{
s[x].v.x+=s[y].v.x;
return x;
}
s[x].ls=merge(s[x].ls,s[y].ls),s[x].rs=merge(s[x].rs,s[y].rs);
s[x].v=max(s[s[x].ls].v,s[s[x].rs].v);
return x;
}
node query(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b) return s[x].v;
int mid=(l+r)>>1;
if(b<=mid) return query(l,mid,s[x].ls,a,b);
if(a>mid) return query(mid+1,r,s[x].rs,a,b);
return max(query(l,mid,s[x].ls,a,b),query(mid+1,r,s[x].rs,a,b));
}
void dfs(int x)
{
for(int i=head[x];i!=-1;i=nxt[i])
{
dfs(to[i]),rt[x]=merge(rt[x],rt[to[i]]);
}
for(it=q2[x].begin();it!=q2[x].end();it++)
{
int a=*it;
ans[a]=query(1,m,rt[x],pl[a],pr[a]);
}
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
scanf("%s",S),n=strlen(S);
m=rd();
int i,j,a,b,u,dep;
tot=1;
for(i=1;i<=m;i++)
{
scanf("%s",T),a=strlen(T);
for(last=1,j=0;j<a;j++) extend(T[j]-'a'),insert(1,m,rt[last],i);
}
Q=rd();
for(i=1;i<=Q;i++)
{
pl[i]=rd(),pr[i]=rd(),sl[i]=rd()-1,sr[i]=rd()-1,q1[sr[i]].push_back(i);
}
memset(head,-1,sizeof(head));
for(i=2;i<=tot;i++) add(pre[i],i),fa[0][i]=pre[i],Log[i]=Log[i>>1]+1;
for(j=1;(1<<j)<=tot;j++) for(i=1;i<=tot;i++) fa[j][i]=fa[j-1][fa[j-1][i]];
for(u=1,dep=0,i=0;i<n;i++)
{
while(u&&!ch[u][S[i]-'a']) u=pre[u],dep=mx[u];
if(!u)
{
u=1,dep=0;
continue;
}
u=ch[u][S[i]-'a'],dep++;
for(it=q1[i].begin();it!=q1[i].end();it++)
{
a=*it,b=u;
if(dep<sr[a]-sl[a]+1) continue;
for(j=Log[mx[u]+1];j>=0;j--) if(mx[fa[j][b]]>=sr[a]-sl[a]+1) b=fa[j][b];
q2[b].push_back(a);
}
}
dfs(1);
for(i=1;i<=Q;i++)
{
if(!ans[i].x) ans[i].y=pl[i];
printf("%d %d\n",ans[i].y,ans[i].x);
}
return 0;
}//popo 2 poq popoqqq 2 3 4