前置知识
线段树合并
本部分转自Parsnip
对于一类问题中,假如我们有若干棵权值线段树,它们都维护相同的值域区间,我们希望能够将这些线段树对应区间的关键值进行相加,同时继续维护区间最大值/最小值等信息,这就需要用到线段树合并算法。
一般来说,我们会用如下的方式来实现线段树合并:
我们用两个指针分别从两个线段树的根节点出发,同步地遍历两棵线段树,并且合并相同区间的有关信息
若之一为空,则以非空的那个节点作为合并后的节点
若均不为空,则递归地合并的左右子节点,左后删除节点,并自底向上更新关键信息,留下节点作为合并后的节点。如果已经递归到了叶节点,直接将关键值相加即可。
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;
}
更多的例题与讲解可以去原作者博客看看。
另外还有个从 钟神博客上放过来的可持久化线段树合并空间复杂度的证明:
可能有锅,欢迎指正。
分成两个部分:
- 将 $n $个节点插进 $n $棵不同的树。
- 合并两棵树,并复制两棵树的公共部分,得到一棵新的树。
第一部分会用到至多$ n⌈log_2n⌉ $个节点。
第二部分中,考虑每个非叶子节点:每一次复制它,它子树内的叶子节点数量一定变多了,所以它被复制的次数至多是它子树内的叶子节点数量。每个叶子至多在 个节点的子树中,所以复制节点的次数至多是 $n⌈log_2n⌉ $次。
SAM-后缀自动机
这个可以直接去LSJ爷爷的博客康康 : 后缀自动机
其他的讲解也很多 自己看看就好了。
有一个本题要用的很基础的套路就是:一个子串的出现次数就是这个子串在SAM上的fail树的子树内的节点个数。(因为子树内的所有点的后缀都包含了当前这个串,而每个节点的相同,所以就是节点个数)
本题思路
首先看到“出现次数最多”,可以想到上面那个套路。那么一个子串在其他串中的出现次数就可以先“定位”子串。(就顺着字典树走出这个,然后向上倍增的跳,走到)
但是这样就出现了一个问题:我们需要对每个上的节点维护所有包含的节点在子树内的出现次数。这样每个节点就需要开一个长度为的数组。显然是会炸掉的。那么我们就需要用到线段树合并维护这个东西就好了。
线段树维护一个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;
}