广义SAM专题的最后一题了……呼
题意：
给出一个长度为$n$的串$S$和$m$个串$T_{1\cdots m}$，给出$q$个询问$l,r,pl,pr$，询问$S[pl\cdots pr]$在$T_l\cdots T_r$中哪个串出现次数最多，出现了多少次。
$1\leq n,q\leq 10^5,1\leq m,\sum|T|\leq 10^4$
串中只会出现小写字母
题解：
神题啊……放图镇楼
先对T串建出广义SAM，然后把S放到上面匹配，求出每个字符所代表的节点，那么每次查询就相当于求这一段字符在SAM上对应的节点的right集合包含的字符串的众数是哪个串，显然这是parent树上的一个子树众数问题；
考虑如何维护right集合在所有$T$中的出现次数，可以对每一个节点开一棵线段树，维护每个T串的出现次数的最大值，这样子在parent树上从下往上线段树合并即可求出right集合；
把询问离线按照右端点排序，把询问标记打在parent树上，最后dfs一遍合并+处理询问即可；
口胡起来不难但是写起来……超爽！
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#define inf 2147483647
#define eps 1e-9
using namespace std;
typedef long long ll;
typedef double db;
struct task{
int v,id;
task(){v=id=;}
friend bool operator <(task a,task b){
return a.v==b.v?a.id>b.id:a.v<b.v;
}
}ans[];
struct qu{
int l,r,ql,qr;
}q[];
struct edge{
int v,next;
}a[];
struct node{
int ls,rs;
task v;
}t[];
int n,m,Q,len,ch,nw=,tote=,tot=,rt=,cnt=,last,head[],rts[],son[][],fa[],mx[],f[][];
vector<int>qrs[];
vector<int>as[];
char st[],tt[];
void add(int u,int v){
a[++tote].v=v;
a[tote].next=head[u];
head[u]=tote;
}
void updata(int &u,int l,int r,int x){
if(!u)u=++cnt;
if(l==r){
t[u].v.v++;
t[u].v.id=x;
return;
}
int mid=(l+r)/;
if(x<=mid)updata(t[u].ls,l,mid,x);
else updata(t[u].rs,mid+,r,x);
t[u].v=max(t[t[u].ls].v,t[t[u].rs].v);
}
void merge(int &x,int y){
if(!x||!y){
x|=y;
return;
}
if(!t[x].ls&&!t[x].rs){
t[x].v.v+=t[y].v.v;
return;
}
merge(t[x].ls,t[y].ls);
merge(t[x].rs,t[y].rs);
t[x].v=max(t[t[x].ls].v,t[t[x].rs].v);
}
task query(int u,int l,int r,int L,int R){
if(L<=l&&r<=R){
return t[u].v;
}
int mid=(l+r)/;
task ret;
if(L<=mid)ret=max(ret,query(t[u].ls,l,mid,L,R));
if(mid<R)ret=max(ret,query(t[u].rs,mid+,r,L,R));
return ret;
}
void extend(int ch){
int p=last,np=++tot;
mx[np]=mx[p]+;
for(;p&&!son[p][ch];p=fa[p])son[p][ch]=np;
if(!p)fa[np]=rt;
else{
int q=son[p][ch];
if(mx[q]==mx[p]+)fa[np]=q;
else{
int nq=++tot;
mx[nq]=mx[p]+;
memcpy(son[nq],son[q],sizeof(son[q]));
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for(;p&&son[p][ch]==q;p=fa[p])son[p][ch]=nq;
}
}
last=np;
}
void dfs(int u){
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
int v=a[tmp].v;
dfs(v);
merge(rts[u],rts[v]);
}
for(int i=,ii=as[u].size();i<ii;i++){
ans[as[u][i]]=query(rts[u],,m,q[as[u][i]].l,q[as[u][i]].r);
}
}
int main(){
memset(head,-,sizeof(head));
scanf("%s%d",st+,&m);
n=strlen(st+);
for(int i=;i<=m;i++){
scanf("%s",tt);
len=strlen(tt);
last=rt;
for(int j=;j<len;j++){
extend(tt[j]-'a');
updata(rts[last],,m,i);
}
}
scanf("%d",&Q);
for(int i=;i<=Q;i++){
scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].ql,&q[i].qr);
qrs[q[i].qr].push_back(i);
}
for(int i=;i<=tot;i++){
f[i][]=fa[i];
add(fa[i],i);
}
for(int j=;j<=;j++){
for(int i=;i<=tot;i++){
f[i][j]=f[f[i][j-]][j-];
}
}
len=;
for(int i=;i<=n;i++){
ch=st[i]-'a';
for(;nw&&!son[nw][ch];)nw=fa[nw],len=mx[nw];
if(!nw){
nw=rt;
len=;
}else{
nw=son[nw][ch];
len++;
for(int j=,jj=qrs[i].size();j<jj;j++){
int v=qrs[i][j];
if(len>=q[v].qr-q[v].ql+){
int _nw=nw;
for(int k=;k>=;k--){
if(mx[f[_nw][k]]>=q[v].qr-q[v].ql+){
_nw=f[_nw][k];
}
}
as[_nw].push_back(v);
}
}
}
}
dfs();
for(int i=;i<=Q;i++){
if(!ans[i].v)ans[i].id=q[i].l;
printf("%d %d\n",ans[i].id,ans[i].v);
}
return ;
}