【Codeforces 666E】Forensic Examination
后缀数组+莫队+值域分块
题目大意：
给定字符串 $s$ 以及 $m$ 个字符串 $t_1\sim t_m$。
有 $q$ 次询问，每次询问给定 $l_1,r_1,l_2,r_2$，询问 $s$ 的子串 $s_{l_1,r_1}$ 在 $t_{l_2}\sim t_{r_2}$ 的哪个串中的出现次数最多，输出串的编号和出现次数。如果有多个串合法，输出编号较小的串。
题解：
后缀数组做法，需要莫队和分块辅助。
考虑把 $s$ 和所有 $t$ 连接成一个大串，中间用不同的分隔字符隔开，然后求它的后缀数组。预处理 height 数组的 ST 表。
对于每个询问，我们可以二分它在后缀数组上 LCP 大于等于子串长度的区间 $[l’,r’]$。这个区间内的每个开头位置，都完整地出现了一次子串。
我们令 $a_i$ 表示后缀数组上排名 $i$ 的后缀的开头位置所在的 $t$ 串的编号。
那么我们对每个询问，转化为询问 $a_{l’}\sim a_{r’}$ 中，值域范围在 $[l_2,r_2]$ 内的数中，出现次数最多的数的出现次数。
考虑莫队，我们可以维护每个数的出现次数，和每个出现次数的出现次数，这样可以求全局众数。
由于有值域限制，所以我们对值域分块，每个块维护一下，值域在这个块中的数的出现次数的出现次数，还有这个值域中的众数出现次数。查询的时候，边角暴力查，中间的直接 $O(1)$ 找到一个众数出现次数最多的块，然后在这个块内查询具体是哪个数即可。
令 $N=|s|+\sum|t|$。
时间复杂度 $O(N\log N+N\sqrt q+q\sqrt N)$。
考虑一些简单的优化。我们发现 $\sum |t|\leqslant 5\times 10^4$，而后缀数组中很大一部分都是 $s$ 的位置。所以我们对 $a$ 数组进行一些处理，把空的位置删掉，那么莫队的时候复杂度就得到了一些优化。
令 $M=\sum |t|$。
时间复杂度 $O(N\log N+M\sqrt q+q\sqrt M)$。可以在 $6$ 秒内通过。
Code：
#include<iostream>
#include<algorithm>
#include<utility>
#include<cmath>
using namespace std;
#define lg(x)(31-__builtin_clz(x))
#define bel(x)((x-1)/256+1)
const int N=8e5+5,M=5e4+5;
char s[N],t[N];
int S[N],m=127,n,len,col[N],height[N],sa[N],x[N],y[N],c[N];
int st[20][N];
int tot[M],ct[258][M],mx[258];
inline int lcp(int l,int r){
if(++l>r)return len;
const int g=lg(r-l+1);
return min(st[g][l],st[g][r-(1<<g)+1]);
}
void ssort(){
for(int i=1;i<=len;++i)++c[x[i]=S[i]];
for(int i=1;i<=m;++i)c[i]+=c[i-1];
for(int i=len;i;--i)sa[c[x[i]]--]=i;
for(int k=1;k<=len;k<<=1){
int p=0;
for(int i=len-k+1;i<=len;++i)
y[++p]=i;
for(int i=1;i<=len;++i)
if(sa[i]>k)y[++p]=sa[i]-k;
for(int i=0;i<=m;++i)c[i]=0;
for(int i=1;i<=len;++i)++c[x[i]];
for(int i=1;i<=m;++i)c[i]+=c[i-1];
for(int i=len;i;--i)sa[c[x[y[i]]]--]=y[i];
swap(x,y);
x[sa[1]]=p=1;
for(int i=2;i<=len;++i)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p);
if(p==len)break;
m=p;
}
for(int i=1,k=0;i<=len;++i)
if(x[i]!=1){
k-=!!k;
int j=sa[x[i]-1];
while(S[i+k]==S[j+k])++k;
height[x[i]]=k;
}
for(int i=1;i<=len;++i)st[0][i]=height[i];
for(int j=1;j<20;++j)
for(int i=1;i+(1<<j-1)<=len;++i)
st[j][i]=min(st[j-1][i],st[j-1][i+(1<<j-1)]);
}
int siz;
pair<int,int>ans[N];
struct que{
int l,r,L,R,id;
inline bool operator<(const que&rhs)const{
return(l/siz!=rhs.l/siz)?l<rhs.l:r<rhs.r;
}
}q[N];
int a[N],k,pos[N];
inline int askL(int pos,int len){
int l=1,r=pos-1,ret=pos;
while(l<=r){
const int mid=l+r>>1;
if(lcp(mid,pos)>=len)r=(ret=mid)-1;else l=mid+1;
}
return ret;
}
inline int askR(int pos,int len){
int l=pos+1,r=::len,ret=pos;
while(l<=r){
const int mid=l+r>>1;
if(lcp(pos,mid)>=len)l=(ret=mid)+1;else r=mid-1;
}
return ret;
}
inline void inc(int x){
const int bl=bel(x);
--ct[bl][tot[x]];
++ct[bl][++tot[x]];
if(tot[x]>mx[bl])mx[bl]=tot[x];
}
inline void dec(int x){
const int bl=bel(x);
--ct[bl][tot[x]];
if(ct[bl][mx[bl]]==0)--mx[bl];
++ct[bl][--tot[x]];
}
inline pair<int,int>ask(int l,int r){
const int bL=bel(l),bR=bel(r);
if(bL==bR){
int mx=-1,id=0;
for(int i=l;i<=r;++i)
if(tot[i]>mx)mx=tot[i],id=i;
return make_pair(id,mx);
}else{
int mx=-1,id=0,blk=-1;
for(int i=l;i<=bL*256;++i)
if(tot[i]>mx)mx=tot[i],id=i;
for(int i=bL+1;i<bR;++i)
if(::mx[i]>mx)mx=::mx[i],blk=i;
if(blk!=-1)
for(int i=(blk-1)*256+1;i<=blk*256;++i)
if(tot[i]==mx){
id=i;break;
}
for(int i=(bR-1)*256+1;i<=r;++i)
if(tot[i]>mx)mx=tot[i],id=i;
return make_pair(id,mx);
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>(s+1);
for(int i=1;s[i];++i)
S[++len]=s[i];
cin>>n;
for(int i=1;i<=n;++i){
S[++len]=++m;
cin>>t;
for(int j=0;t[j];++j)
S[++len]=t[j],col[len]=i;
}
ssort();
for(int i=1;i<=len;++i){
if(col[sa[i]]!=0)a[++k]=col[sa[i]];
pos[sa[i]]=k;
}
int Q;
cin>>Q;
for(int i=1;i<=Q;++i){
int l,r,L,R;
cin>>q[i].L>>q[i].R>>l>>r;
const int ln=r-l+1;
L=askL(x[l],ln),R=askR(x[l],ln);
if(col[sa[L]]!=0)L=pos[sa[L]];else L=pos[sa[L]]+1;
R=pos[sa[R]];
if(L>R)q[i].l=1,q[i].r=0;else
q[i].l=L,q[i].r=R;
q[i].id=i;
}
siz=k/(sqrt(Q)+1)+1;
sort(q+1,q+Q+1);
for(int i=1,l=1,r=0;i<=Q;++i){
while(r<q[i].r)inc(a[++r]);
while(l>q[i].l)inc(a[--l]);
while(l<q[i].l)dec(a[l++]);
while(r>q[i].r)dec(a[r--]);
ans[q[i].id]=ask(q[i].L,q[i].R);
}
for(int i=1;i<=Q;++i)
cout<<ans[i].first<<' '<<ans[i].second<<'\n';
return 0;
}