前置知识

线段树合并

本部分转自Parsnip

对于一类问题中，假如我们有若干棵权值线段树，它们都维护相同的值域区间$[1,n]$，我们希望能够将这些线段树对应区间的关键值进行相加，同时继续维护区间最大值/最小值等信息，这就需要用到线段树合并算法。

一般来说，我们会用如下的方式来实现线段树合并：

我们用两个指针$p,q$分别从两个线段树的根节点出发，同步地遍历两棵线段树，并且合并相同区间的有关信息

1. 若$p,q$之一为空，则以非空的那个节点作为合并后的节点

2. 若$p,q$均不为空，则递归地合并$p,q$的左右子节点，左后删除节点$q$，并自底向上更新关键信息，留下节点$p$作为合并后的节点。如果已经递归到了叶节点，直接将关键值相加即可。

Code：

//不可持久化
inline int merge(int p,int q,int l,int r)//两个指针为p，q，当前节点维护的区间为[l,r]
{
    if ( !p || !q ) return p|q;
    if ( l == r )
    {
        cnt(p) += cnt(q);
        return p;
    }
    int mid = l+r >> 1;
    ls(p) = merge( ls(p) , ls(q) , l , mid );
    rs(p) = merge( rs(p) , rs(q) , mid+1 , r );
    updata(p);
    return p;
}

//可持久化
int merge(int x,int y,int l,int r) {
        if(!x||!y)return x|y;
        if(l==r){sum[x]+=sum[y];return x;}
        int mid=(l+r)>>1,z=++cnt;
        ls[z]=merge(ls[x],ls[y],l,mid);
        rs[z]=merge(rs[x],rs[y],mid+1,r);
        pushup(z);
        return z;
    }

更多的例题与讲解可以去原作者博客看看。

另外还有个从 钟神博客上放过来的可持久化线段树合并空间复杂度的证明：

可能有锅，欢迎指正。

分成两个部分：

1. 将 $n $个节点插进 $n $棵不同的树。
2. 合并两棵树，并复制两棵树的公共部分，得到一棵新的树。

第一部分会用到至多$ n⌈log_2⁡n⌉ $个节点。

第二部分中，考虑每个非叶子节点：每一次复制它，它子树内的叶子节点数量一定变多了，所以它被复制的次数至多是它子树内的叶子节点数量。每个叶子至多在$⌈log_2⁡n⌉$ 个节点的子树中，所以复制节点的次数至多是 $n⌈log_2⁡n⌉ $次。

SAM-后缀自动机

这个可以直接去LSJ爷爷的博客康康 : 后缀自动机

其他的讲解也很多 自己看看就好了。

有一个本题要用的很基础的套路就是：一个子串的出现次数就是这个子串在SAM上的fail树的子树内的节点个数。（因为子树内的所有点的后缀都包含了当前这个串，而每个节点的$endpose$相同，所以就是节点个数）

本题思路

首先看到“出现次数最多”，可以想到上面那个套路。那么一个子串在其他串中的出现次数就可以先“定位”子串。（就顺着字典树走出这个$S[1，p_r]$，然后向上倍增的跳，走到$S[p_l,p_r]$）

但是这样就出现了一个问题：我们需要对每个$SAM$上的节点维护所有$T_i$包含的节点在子树内的出现次数。这样每个节点就需要开一个长度为$m$的数组。显然是会炸掉的。那么我们就需要用到线段树合并维护这个东西就好了。

线段树维护一个pair，第一个元素记录出现次数的最大值，第二个元素记录最大值是哪个子串即可。因为这是个权值线段树，所以非叶子节点就记录区间内出现次数最多的那个叶子就好了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=1e6+2e5+1000;

struct segment_tree{
	pii ori[maxn<<4];//???? ??????? 
	int ls[maxn<<4],rs[maxn<<4],cnt;
	segment_tree(){cnt=0;}
	void push_up(int rt)
	{ori[rt]=max(ori[ls[rt]],ori[rs[rt]]);}
	int merge(int rt1,int rt2,int l,int r){
		if(!rt1||!rt2)return rt1|rt2;
		int cur=++cnt;
		if(l==r){
			ori[cur]=ori[rt1];ori[cur].fi+=ori[rt2].fi;
			return cur;
		}
		int mid=(l+r)>>1;
		ls[cur]=merge(ls[rt1],ls[rt2],l,mid);
		rs[cur]=merge(rs[rt1],rs[rt2],mid+1,r);
		push_up(cur);
		return cur;
	}
	int add(int l,int r,int rt,int tar,int val){
		if(!rt){rt=++cnt;}
		if(l==r){
			ori[rt].se=-l;ori[rt].fi+=val;return rt;
		}
		int mid=(l+r)>>1;
		if(tar<=mid)ls[rt]=add(l,mid,ls[rt],tar,val);
		if(tar>=mid+1)rs[rt]=add(mid+1,r,rs[rt],tar,val);
		push_up(rt);
		return rt;
	}
	pii query(int l,int r,int rt,int tl,int tr){
		if(tl<=l&&r<=tr){return ori[rt];}
		int mid=(l+r)>>1;
		pii tmp=mk(0,0);
		if(tl<=mid)tmp=max(tmp,query(l,mid,ls[rt],tl,tr));
		if(tr>=mid+1)tmp=max(tmp,query(mid+1,r,rs[rt],tl,tr));
		return tmp;
	}

}t;
int rt[maxn];
int n;
struct SAM{
	int ch[maxn][27],link[maxn],cnt,last,len[maxn],pos[maxn];//pos?????????????????¦Ë?? 
	SAM(){cnt=last=1;}
	void insert(int c){
		int p=last,cur=++cnt;len[cur]=len[last]+1;
		while(p&&!ch[p][c])ch[p][c]=cur,p=link[p];
		if(!p)link[cur]=1;
		else{
			int q=ch[p][c];
			if(len[p]+1==len[q])link[cur]=q;
			else{
				int cl=++cnt;len[cl]=len[p]+1;
				memcpy(ch[cl],ch[q],sizeof(ch[cl]));
				link[cl]=link[q];
				link[q]=link[cur]=cl;
				while(p&&ch[p][c]==q){ch[p][c]=cl,p=link[p];}
			}
		}
		last=cur;
	}
	vi side[maxn];int f[maxn][23];
	void addall(){
		rep(i,2,cnt)side[link[i]].pb(i);
	}
	void dfs(int u,int fa){
		//int top=0,stk[100]={0};	
		f[u][0]=fa;
		for(int i=0;i<side[u].size();i++){
			int v=side[u][i];dfs(v,u);rt[u]=t.merge(rt[v],rt[u],1,n);
			//cout<<v<<' ';
			//stk[++top]=v;
		}
		//cout<<"Now :"<<u<<"  Son: ";
		//rep(i,1,top)cout<<u<<' '<<stk[i]<<' '<<endl;
		//cout<<endl;
	}
	void init(){
		rep(j,1,22)rep(i,1,cnt)f[i][j]=f[f[i][j-1]][j-1];
	}
	int jump(int x,int l){
		for(int i=22;i>=0;i--)if(len[f[x][i]]>=l)x=f[x][i];
		return x;
	}
}sam;

char m[maxn],s[maxn];

int main(){
//	freopen("in","r",stdin);
	scanf("%s",m+1);int len=strlen(m+1);
	rep(i,1,len){
		sam.insert(m[i]-'a');sam.pos[i]=sam.last;
	}
	scanf("%d",&n);
	rep(i,1,n){
		scanf("%s",s+1);len=strlen(s+1);sam.last=1;
		rep(j,1,len){
			sam.insert(s[j]-'a');
			rt[sam.last]=t.add(1,n,rt[sam.last],i,1);
		}
	}
	sam.addall();
	sam.dfs(1,0);
	sam.init();
	int q;scanf("%d",&q);
	rep(i,1,q){
		int l,r,pl,pr;scanf("%d%d%d%d",&l,&r,&pl,&pr);
		int x=sam.pos[pr];
		x=sam.jump(x,pr-pl+1);
		pii ans=t.query(1,n,rt[x],l,r);
		if(!ans.fi)printf("%d %d\n",l,ans.fi);
		else printf("%d %d\n",-ans.se,ans.fi);
	}
	return 0;
}