[NOI2018]你的名字
苍天啊，大地啊，模拟赛里怎么全是毒瘤题啊！
题目链接：luoguP4770。
这道题让我们求的是 $ t $ 所有本质不同子串中不为 $ S[l,r] $ 的子串的个数。
首先我们可以利用 SAM 非常简单的求出 $ t $ 的本质不同子串个数。
什么？你不知道怎么求，建议先做luoguP3804 【模板】后缀自动机 (SAM)
下面我们只需要对每一个询问求出包含在 $ S[l,r] $ 中的 $ t $ 的所有本质不同子串个数就可以了。
68分做法
我们可以看到，整道题前面 $ 68 $ 分都有 $ l=1,r=|S| $ ，我们不妨先来思考这些测试点怎么做。
如果我们想要知道 $ t $ 的哪些子串同时也是 $ S $ 的子串，最好的方法肯定就是对 $ |S| $ 建立一个 SAM，然后用 $ t $ 在上面匹配。
因为SAM的fail的含义于AC自动机的差不多，指向的都是该节点代表字符串的后缀。
并且SAM中包含一个字符串的所有子串，就相当于是把一个字符串的所有子串抽出来建了一个AC自动机。
所以实际上是可以进行匹配的（可能还挺常用？）。
这样子我们就可以知道对于 $ t $ 的每一个前缀 $ t[1,i] $ ，它的最长后缀的长度使得这个后缀是 $ S $ 的子串。
但是这样找出的子串并不能保证本质不同。
那么我们把这个过程搬到 SAM 上面。
我们再对 $ t $ 建一个 SAM，并且对于每一个点 $ i $ 再新维护一个信息 $ val_i $ ，表示第 $ i $ 个点表示的所有字符串中，长度小于等于 $ val_i $ 的都是 $ S $ 的子串。
我们只需要把 $ t $ 在 $ S $ 的 SAM 上面跑一遍，然后顺着 parent 边更新答案就可以了（拓扑排序或者dfs都行）。
其实上面找 $ val_i $ 的过程事实上就是这道题，可以做一下加深理解。
然后我们就可以拿到 $ 68 $ 分了！
满分做法
我们发现，上面的做法不能AC主要原因在于每一次询问的是 $ S $ 的一个子串，我们使用 $ t $ 进行匹配的时候很有可能“越界”，而我们又不能快速得到 $ S $ 的某个子串的SAM。
我们无法快速得到一个子串的SAM，那我们能否快速查询某一个节点代表的某个子串是否在 $ [l,r] $ 范围内呢？
我们知道，SAM上某一个节点代表字符串的位置实际上是和它的 endpos 有关的，那么我们能不能快速得到某个节点的 endpos 集合呢？
答案是可以的，我们需要在SAM的parent上面跑线段树合并。
所以我们只需要在沿边转移的时候加上一个endpos的条件即可。
停停，线段树合并不是离线的吗？
所以我们需要进行可持久化线段树合并。
和普通线段树合并不同的一点是，我们每次合并两个节点时新建一个节点，这样就不会破坏原来的节点，并且在所有查询之前进行合并，这样时间复杂度不会变，算法也变成了在线。
然后快乐提交，拿到 $ 97 $ 分，挂了一个点。
代码
提交记录
哪里挂了呢？
你会发现假如某一个节点因为endpos而不能转移时，你直接跳了fail，但是有可能在匹配长度减小一些以后它又可以转移了。
稍微转移一下就可以过。
代码：
#include
#include
#include
#include
using namespace std;
template
using vc=vector;
using pi=pair;
using ll=long long;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int root[1000001];
vcg[1000001];
int ls[30000001];
int rs[30000001];
int son[2000001][26];
int fail[2000001];
int len[2000001];
vct[100001];
vcw[100001];
char in[1000002];
int mo[2000001];
int ma[2000001];
char s[500002];
ll ans[100001];
int l[100001];
int r[100001];
int cnt=1;
int lst=1;
int tot;
int n,m;
void clear()
{
for(int i=1;i<=cnt;i++)
{
fail[i]=len[i]=ma[i]=0;
for(int j=0;j<26;j++) son[i][j]=0;
}
cnt=lst=1;
}
void add(int a)
{
int cur=++cnt,p=lst;lst=cur,len[cur]=len[p]+1;
for(;p&&!son[p][a];p=fail[p]) son[p][a]=cur;
if(!p){ fail[cur]=1;return ;}
int q=son[p][a];
if(len[q]==len[p]+1){ fail[cur]=q;return ;}
int nq=++cnt;len[nq]=len[p]+1;
fail[nq]=fail[q],fail[q]=fail[cur]=nq;
for(int i=0;i<26;i++) son[nq][i]=son[q][i];
for(;p&&son[p][a]==q;p=fail[p]) son[p][a]=nq;
}
void debug()
{
// for(int i=1;i<=cnt;i++)
// {
// printf("%d : len=%d fail=%d ",i,len[i],fail[i]);
// for(int j=0;j<26;j++) if(son[i][j]) printf("(%c,%d) ",j+'a',son[i][j]);
// printf("\n");
// }
}
void add(int &p,int pl,int pr,int x)
{
if(!p) p=++tot;
if(pl==pr) return ;
int mid=(pl+pr)>>1;
if(x<=mid) add(ls[p],pl,mid,x);
else add(rs[p],mid+1,pr,x);
}
int merge(int u,int v,int pl,int pr)
{
if(!u||!v) return u|v;
int ans=++tot;
if(pl==pr) return ans;
int mid=(pl+pr)>>1;
ls[ans]=merge(ls[u],ls[v],pl,mid);
rs[ans]=merge(rs[u],rs[v],mid+1,pr);
return ans;
}
void dfs(int num)
{
for(int p:g[num]) dfs(p),root[num]=merge(root[num],root[p],1,m);
}
void topo()
{
queueque;
for(int i=2;i<=cnt;i++) mo[fail[i]]++;
for(int i=1;i<=cnt;i++) if(!mo[i]) que.push(i);
while(!que.empty())
{
int p=que.front();que.pop();
ma[fail[p]]=max(ma[fail[p]],ma[p]),mo[fail[p]]--;
if(!mo[fail[p]]) que.push(fail[p]);
}
}
bool get(int p,int pl,int pr,int l,int r)
{
// printf("get %d %d %d %d %d\n",p,pl,pr,l,r);
if(!p) return false;
if(l<=pl&&pr<=r) return true;
int mid=(pl+pr)>>1;
if(l<=mid&&get(ls[p],pl,mid,l,r)) return true;
if(mid %d\n",le,le-1);
le--;
if(len[fail[now]]==le) now=fail[now];
}
w[i].push_back(le);
// printf("j=%d : now=%d le=%d\n",j,now,le);
// printf("%d ",le);
}
// printf("\n");
}
for(int i=1;i<=n;i++)
{
clear();
for(unsigned j=0;j