多数题目都是套路。用到的技巧在我的垃圾讲解里多少也有涉及。
当然也是有大神题的。。。
因为7道题之前就做过（品酒大会在题库刷3倍经验的时候不小心水掉了）
然后剩下3道都是大神题。。。根本做不动。。。
至少现在套路应该也都会了，也算是捡回来了吧
弦论：
$Description:$
对于一个给定长度为N的字符串，求它的第K小子串是什么。相同的子串算1次或多次。$N le 10^5,K le 10^9$
建出SAM。拓扑dp得到「从这个点出发可以形成多少种子串」和「从这个点出发可以形成多少个子串」
然后贪心的跑。
1 #include<cstdio> 2 int len[1000005],c[1000005][26],f[1000005],cnt=1,lst=1,dp[1000005],n,L,t,tot[1000005]; 3 char s[500005],ans[500005]; 4 void insert(int x){ 5 int p=lst,np;np=lst=++cnt; 6 len[np]=len[p]+1;dp[np]=1; 7 for(;p&&!c[p][x];p=f[p])c[p][x]=np; 8 if(!p)f[np]=1; 9 else{ 10 int q=c[p][x]; 11 if(len[q]==len[p]+1)f[np]=q; 12 else{ 13 int nq=++cnt;f[nq]=f[q];len[nq]=len[p]+1; 14 for(int i=0;i<26;++i)c[nq][i]=c[q][i]; 15 f[q]=f[np]=nq; 16 for(;c[p][x]==q;p=f[p])c[p][x]=nq; 17 } 18 } 19 } 20 int ec,fir[1000005],l[1000005],to[1000005],k; 21 void link(int a,int b){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;} 22 void dfs(int p){ 23 for(int i=fir[p];i;i=l[i])dfs(to[i]),dp[p]+=dp[to[i]]; 24 if(!t)dp[p]=1;//printf("%d %d ",p,dp[p]); 25 } 26 void Dfs(int p){ 27 if(tot[p])return; 28 for(int i=0;i<26;++i)if(c[p][i])Dfs(c[p][i]),tot[p]+=dp[c[p][i]]+tot[c[p][i]]; 29 } 30 void DFS(int p,int k){ 31 k-=dp[p];if(k<=0)return;//printf("%d %d ",p,k); 32 for(int i=0;i<27;++i)if(c[p][i]) 33 if(k>tot[c[p][i]]+dp[c[p][i]])k-=tot[c[p][i]]+dp[c[p][i]]; 34 else {ans[++L]='a'+i,DFS(c[p][i],k);return;} 35 } 36 int main(){ 37 scanf("%s",s+1); 38 while(s[n+1])n++; 39 for(int i=1;i<=n;++i)insert(s[i]-'a'); 40 for(int i=2;i<=cnt;++i)link(f[i],i);//,printf("%d %d ",f[i],i); 41 scanf("%d%d",&t,&k); 42 dfs(1);Dfs(1);dp[1]=0;DFS(1,k); 43 puts(ans+1); 44 }
诸神眷顾的幻想乡：
$Description:$
幽香是全幻想乡里最受人欢迎的萌妹子，这天，是幽香的2600岁生日，无数幽香的粉丝到了幽香家门前的太阳花田上来为幽香庆祝生日。
粉丝们非常热情，自发组织表演了一系列节目给幽香看。幽香当然也非常高兴啦。
这时幽香发现了一件非常有趣的事情，太阳花田有n块空地。在过去，幽香为了方便，在这n块空地之间修建了n-1条边将它们连通起来。也就是说，这 块空地形成了一个树的结构。
有n个粉丝们来到了太阳花田上。为了表达对幽香生日的祝贺，他们选择了c中颜色的衣服，每种颜色恰好可以用一个1到c之间的整数来表示。并且每个人都站在一个空地上，每个空地上也只有一个人。这样整个太阳花田就花花绿绿了。幽香看到了，感觉也非常开心。
粉丝们策划的一个节目是这样的，选中两个粉丝A和B（可以相同），然后A所在的空地到B所在的空地的路径上的粉丝依次跳起来（包括端点）.幽香就能看到一个长度为A到B之间路径上的所有粉丝的数目（包括A和B）的颜色序列。
一开始大家打算让人一两个粉丝（注意： 和 是不同的，他们形成的序列刚好相反，比如红绿蓝和蓝绿红）都来一次，但是有人指出这样可能会出现一些一模一样的颜色序列，会导致审美疲劳。
于是他们想要问题，在这个树上，一共有多少可能的不同的颜色序列（子串）幽香可以看到呢？
太阳花田的结构比较特殊，只与一个空地相邻的空地数量不超过20个。$n le 10^5,c le 10$
广义后缀自动机。我写的比较暴力。
枚举所有190条路径，全都塞进SAM里就可以了。
更好的做法是以每个叶节点为根建20个trie。这样就不会被卡了。
然而其实第一种也不会被卡。
1 #include<cstdio> 2 int cnt=1,lst=1,f[4000005],c[4000005][11],len[4000004],s[200005],n,C,w[200005]; 3 long long ans; 4 void insert(int x){ 5 int p=lst,np;lst=np=++cnt;len[np]=len[p]+1; 6 for(;p&&!c[p][x];p=f[p])c[p][x]=np; 7 if(!p)f[np]=1; 8 else{ 9 int q=c[p][x]; 10 if(len[q]==len[p]+1)f[np]=q; 11 else { 12 int nq=++cnt;f[nq]=f[q]; 13 for(int i=0;i<=10;++i)c[nq][i]=c[q][i]; 14 f[np]=f[q]=nq;len[nq]=len[p]+1; 15 for(;p&&c[p][x]==q;p=f[p])c[p][x]=nq; 16 } 17 } 18 } 19 int fir[200005],l[400005],to[400005],ec,deg[200005]; 20 void link(int a,int b){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;deg[b]++;} 21 void dfs(int p,int fa,int len){ 22 s[len]=w[p]; 23 if(deg[p]==1&&len!=1){lst=1;for(int i=1;i<=len;++i)insert(s[i]);} 24 for(int i=fir[p];i;i=l[i])if(to[i]!=fa)dfs(to[i],p,len+1); 25 } 26 int main(){ 27 scanf("%d%d",&n,&C); 28 for(int i=1;i<=n;++i)scanf("%d",&w[i]); 29 for(int i=1,x,y;i<n;++i)scanf("%d%d",&x,&y),link(x,y),link(y,x); 30 for(int i=1;i<=n;++i)if(deg[i]==1)dfs(i,0,1); 31 for(int i=1;i<=cnt;++i)ans+=len[i]-len[f[i]]; 32 printf("%lld ",ans); 33 }
公共串：
$Description:$
给出几个由小写字母构成的单词，求它们最长的公共子串的长度。$N le 5,|S| le 2000$
对于第一个串建出SAM，剩下的串都放在上面跑。
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 int n,c[4005][26],f[4005],len[4005],cnt=1,lst=1,ans,mtc[4005][6];char s[4005]; 5 void insert(int x){ 6 int p=lst,np;lst=np=++cnt; 7 len[np]=len[p]+1; 8 for(;p&&!c[p][x];p=f[p])c[p][x]=np; 9 if(!p)f[np]=1; 10 else{ 11 int q=c[p][x]; 12 if(len[q]==len[p]+1)f[np]=q; 13 else{ 14 int nq=++cnt;len[nq]=len[p]+1;f[nq]=f[q]; 15 for(int i=0;i<26;++i)c[nq][i]=c[q][i]; 16 f[q]=f[np]=nq; 17 for(;p&&c[p][x]==q;p=f[p])c[p][x]=nq; 18 } 19 } 20 } 21 main(){ 22 scanf("%d%s",&n,s); 23 for(int i=0;s[i];++i)insert(s[i]-'a'); 24 for(int i=2,p,m;i<=n;++i){ 25 scanf("%s",s);p=1;m=0; 26 for(int ch=0;s[ch];++ch){ 27 while(p&&!c[p][s[ch]-'a'])p=f[p],m=len[p]; 28 p=c[p][s[ch]-'a']; m++; mtc[p][i]=max(mtc[p][i],m); 29 if(!p)p=1,m=0; 30 for(int q=f[p];q;q=f[q])mtc[q][i]=max(mtc[q][i],len[q]); 31 } 32 } 33 for(int p=1;p<=cnt;++p){ 34 int x=10000; 35 for(int i=2;i<=n;++i)x=min(mtc[p][i],x); 36 ans=max(ans,x); 37 } 38 cout<<ans<<endl; 39 }
差异：
$Description:$
一个长度为n的字符串S，令$T_i$表示它从第i个字符开始的后缀。求所有串两两之间非lcp部分的和
2<=N<=500000
$lcp$就是所有后缀所在的节点的$lca$的$len$。然后就是树上合并，看有多少特殊点对以特定点为$lca$
1 #include<cstdio> 2 char s[500005];int lst=1,cnt=1,f[1000005],c[1000005][26],dp[1000005],len[1000005];long long ans; 3 void insert(int x){ 4 int p=lst,np;lst=np=++cnt;len[np]=len[p]+1;dp[np]=1; 5 for(;p&&!c[p][x];p=f[p])c[p][x]=np; 6 if(!p)f[np]=1; 7 else{ 8 int q=c[p][x]; 9 if(len[q]==len[p]+1)f[np]=q; 10 else{ 11 int nq=++cnt;f[nq]=f[q]; 12 for(int i=0;i<26;++i)c[nq][i]=c[q][i]; 13 f[np]=f[q]=nq;len[nq]=len[p]+1; 14 for(;c[p][x]==q;p=f[p])c[p][x]=nq; 15 } 16 } 17 } 18 int fir[1000005],l[1000005],to[1000005],ec; 19 void link(int a,int b){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;} 20 void dfs(int p){ 21 for(int i=fir[p];i;i=l[i]){ 22 int S=to[i];dfs(S); 23 ans-=2ll*len[p]*dp[S]*dp[p]; 24 dp[p]+=dp[S]; 25 } 26 } 27 int main(){ 28 int n=0; 29 scanf("%s",s+1); 30 while(s[n+1])++n; 31 for(int i=1;i<=n;++i)insert(s[n-i+1]-'a'); 32 ans+=(n+1ll)*n*(n-1)>>1; 33 for(int i=1;i<=cnt;++i)if(f[i])link(f[i],i); 34 dfs(1);printf("%lld ",ans); 35 }
工艺：
$Description:$
小敏和小燕是一对好朋友。
他们正在玩一种神奇的游戏，叫Minecraft。
他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。
他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。
两个工艺品美观的比较方法是，从头开始比较，如果第i个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第i+1个方块。如果全都一样，那么这两个工艺品就一样漂亮。$N le 300000$
循环位移最小字典序。断环成链然后找字典序最小的长度为n的子串。
1 #include<cstdio> 2 #include<map> 3 using namespace std; 4 int n,x[300005],f[1200005],lst=1,cnt=1,len[1200005]; 5 map<int,int>c[1200005]; 6 void insert(int x){ 7 int p=lst,np;lst=np=++cnt;len[np]=len[p]+1; 8 for(;p&&!c[p][x];p=f[p])c[p][x]=np; 9 if(!p)f[np]=1; 10 else{ 11 int q=c[p][x]; 12 if(len[q]==len[p]+1)f[np]=q; 13 else{ 14 int nq=++cnt;c[nq]=c[q];f[nq]=f[q];len[nq]=len[p]+1; 15 f[q]=f[np]=nq; 16 for(;p&&c[p][x]==q;p=f[p])c[p][x]=nq; 17 } 18 } 19 } 20 int main(){ 21 scanf("%d",&n); 22 for(int i=1;i<=n;++i)scanf("%d",&x[i]),insert(x[i]); 23 for(int i=1;i<=n;++i)insert(x[i]); 24 for(int i=1,p=1;i<=n;++i)printf("%d ",(*c[p].begin()).first),p=(*c[p].begin()).second; 25 }
生成魔咒：
$Description:$
魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符1、2拼凑起来形成一个魔咒[1,2]。
一个魔咒串的非空子串被称为魔咒串的生成魔咒。
例如[1,2,1]时，它的生成魔咒有[1]、[2]、[1,2]、[2,1]、[1,2,1] 五种
最初为空串。共进行n次操作，每次操作是在结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串共有多少种生成魔咒。
$n le 10^5$
加入字符，查询本质不同子串数。每次新增的就是$len[np]-len[f[np]]$
1 #include<cstdio> 2 #include<map> 3 using namespace std; 4 int f[200005],len[200005],cnt=1,lst=1,np,p;long long ans; 5 map<int,int>c[200005]; 6 void insert(int x){ 7 p=lst;np=lst=++cnt;len[np]=len[p]+1; 8 for(;p&&!c[p][x];p=f[p])c[p][x]=np; 9 if(!p)f[np]=1; 10 else{ 11 int q=c[p][x]; 12 if(len[q]==len[p]+1)f[np]=q; 13 else{ 14 int nq=++cnt;c[nq]=c[q];f[nq]=f[q]; 15 len[nq]=len[p]+1;f[q]=f[np]=nq; 16 for(;p&&c[p][x]==q;p=f[p])c[p][x]=nq; 17 } 18 }ans+=len[np]-len[f[np]]; 19 } 20 int main(){ 21 int n,x;scanf("%d",&n); 22 while(n--)scanf("%d",&x),insert(x),printf("%lld ",ans); 23 }
Substring：
$Description:$
懒得写背景了，给你一个字符串，要求你支持两个操作
(1):在当前字符串的后面插入一个字符串 (2):询问字符串$s$在当前字符串中出现了几次？(作为连续子串) 你必须在线支持这些操作。
总长$le 6 imes 10^5$,询问$le 10^4$，询问总长$le 3 imes 10^6$
动态加字符，查询$endpos$大小。
就是维护$firstpos$的子树并。也就是每次新建$np$时这个点有1权，然后就是带换父亲的查询子树和。
转化一下，其实就是每个实点都会为祖先贡献1。转化成链上加，单点求值。$LCT$
每次换父亲时去掉子树的贡献。写了个不换根$LCT$常数还巨大
细节不少。数据特别水。稍考验码力。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define S 1333333 4 struct LCT{ 5 int f[S],c[2][S],w[S],lz[S],q[S]; 6 #define lc c[0][p] 7 #define rc c[1][p] 8 bool nr(int p){return c[0][f[p]]==p|c[1][f[p]]==p;} 9 void down(int p){w[lc]+=lz[p];w[rc]+=lz[p];lz[lc]+=lz[p];lz[rc]+=lz[p];lz[p]=0;} 10 void rotate(int p){ 11 int fa=f[p],gr=f[fa],dir=c[1][fa]==p,br=c[!dir][p]; 12 if(nr(fa))c[c[1][gr]==fa][gr]=p; c[!dir][p]=fa; c[dir][fa]=br; 13 f[f[f[br]=fa]=p]=gr; 14 } 15 void splay(int p){ 16 int fa,gr,tp,r=p;q[tp=1]=p; 17 while(nr(r))q[++tp]=r=f[r]; while(tp)down(q[tp--]); 18 while(nr(p)){fa=f[p];gr=f[fa]; 19 if(nr(fa))rotate(c[1][fa]==p^c[1][gr]==fa?p:fa); rotate(p); 20 } 21 } 22 void access(int p){int s=p;for(int r=0;p;p=f[r=p])splay(p),rc=r;splay(s);} 23 void link(int a,int b){splay(a);splay(b);f[a]=b;} 24 void cut(int p){access(p);f[lc]=0;lc=0;} 25 void add(int p,int v){access(p);lz[p]+=v;} 26 int ask(int p){access(p);return w[p];} 27 }T; 28 int c[26][S],f[S],lst=1,pc=1,v[S],n,len[S],M;char s[S<<2],o[9]; 29 void Fa(int p,int fa){int x=T.ask(p);T.add(p,-x);T.cut(p);T.link(p,fa);T.add(p,x);f[p]=fa;} 30 void insert(int C){ 31 int p=lst,q,nq,np=lst=++pc;T.w[np]=v[np]=1; 32 for(;p&&!c[C][p];p=f[p])c[C][p]=np; 33 if(!p){Fa(np,1);return;} 34 if(len[q=c[C][p]]==len[p]+1){Fa(np,q);return;} 35 nq=++pc; len[nq]=len[p]+1; for(int i=0;i<26;++i)c[i][nq]=c[i][q]; 36 Fa(nq,f[q]); Fa(np,nq); Fa(q,nq); 37 for(;p&&c[C][p]==q;p=f[p])c[C][p]=nq; 38 } 39 void DC(int m,int len){for(int i=0;i<len;++i)m=(m*131+i)%len,swap(s[i],s[m]);} 40 int main(){//freopen("1.in","r",stdin); 41 scanf("%d%s",&n,s); 42 for(int i=0;s[i];++i)insert(s[i]-'A'); 43 while(n--){int l=0,p=1; 44 scanf("%s%s",o,s);for(;s[l];++l);DC(M,l); 45 if(o[0]=='A')for(int i=0;i<l;++i)insert(s[i]-'A'); 46 else{ 47 for(int i=0;i<l;++i)p=c[s[i]-'A'][p]; 48 printf("%d ",p?T.ask(p):0);M^=p?T.w[p]:0; 49 } 50 } 51 }
Cheat：
$Description:$
阿米巴是小强的好朋友。
在小强眼中，阿米巴是一个作文成绩很高的文艺青年。为了获取考试作文的真谛，小强向阿米巴求教。阿米巴给小强展示了几篇作文，小强觉得这些文章怎么看怎么觉得熟悉，仿佛是某些范文拼拼凑凑而成的。小强不禁向阿米巴投去了疑惑的眼光，却发现阿米巴露出了一个狡黠的微笑。
为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”，小强想出了一个评定作文 “熟悉程度”的量化指标：L 0 .小强首先将作文转化成一个 01 串。之后，小强搜集了各路名家的文章，同样分别转化成 01 串后，整理出一个包含了 M 个 01 串的“ 标准作文库 ”。
小强认为：如果一个 01 串长度不少于 L 且在 标准作文库 中的某个串里出现过（即，它是 标准作文库 的 某个串 的一个 连续子串 ），那么它是“ 熟悉 ”的。对于一篇作文（一个 01 串）A，如果能够把 A 分割成若干段子串，其中“ 熟悉 ” 的子串的 长度 总 和 不少于 A 总 长度的 90%，那么称 A 是 “ 熟悉的文章 ”。 L 0 是 能够让 A 成为 “ 熟悉的文章 ” 的 所有 L 的最大值 （如果不存在这样的 L，那么规定 L 0 =0）。输入文件的长度不超过 1100000 字节
有最优决策问题。需要$dp$
设$dp_i$表示到$i$为止最多匹配了多少位
那么就有$dp_i=max(dp_{i-1},dp_j + i-j),j in [i-match[i],i-k]$
把串放在广义$SAM$上硬跑得到$match$。而$i-match[i]$肯定是单调不减的。
所以其实就是单调队列优化一下就可以了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define S 2222222 4 int n,m,c[2][S],f[S],mt[S],len[S],pc=1,lst=1,dp[S],q[S];char s[S]; 5 void insert(int C){ 6 int p=lst,q,np,nq; 7 if(q=c[C][lst]){ 8 if(len[q]==len[p]+1){lst=q;return;} 9 lst=nq=++pc; len[nq]=len[p]+1; c[0][nq]=c[0][q]; c[1][nq]=c[1][q]; 10 f[nq]=f[q]; f[q]=nq; for(;p&&c[C][p]==q;p=f[p])c[C][p]=nq; 11 }else{ 12 lst=np=++pc; len[np]=len[p]+1; 13 for(;p&&!c[C][p];p=f[p])c[C][p]=np; 14 if(!p){f[np]=1;return;} q=c[C][p]; 15 if(len[q]==len[p]+1){f[np]=q;return;} 16 len[nq=++pc]=len[p]+1; c[0][nq]=c[0][q]; c[1][nq]=c[1][q]; 17 f[nq]=f[q]; f[q]=f[np]=nq; 18 for(;p&&c[C][p]==q;p=f[p])c[C][p]=nq; 19 } 20 } 21 bool chk(int L,int l){ 22 int h=1,t=0; 23 for(int i=1;i<=l;++i){ 24 if(i>=L){while(h<=t&&dp[q[t]]-q[t]<=dp[i-L]-i+L)t--;q[++t]=i-L;} 25 while(h<=t&&q[h]<i-mt[i])h++; 26 dp[i]=max(dp[i-1],h<=t?dp[q[h]]+i-q[h]:0); 27 }return dp[l]*10>=l*9; 28 } 29 int main(){ 30 scanf("%d%d",&n,&m); 31 for(int i=1;i<=m;++i){ 32 scanf("%s",s);lst=1; 33 for(int p=0;s[p];++p)insert(s[p]^48); 34 } 35 for(int i=1;i<=n;++i){ 36 scanf("%s",s+1);int l=1; 37 for(int p=1,m=0;s[l];++l){ 38 while(!c[s[l]^48][p])p=f[p],m=len[p]; 39 p=c[s[l]^48][p];m++; 40 if(!p)p=1,m=0;mt[l]=m; 41 }l--; 42 int L=1,R=l,ans=0; 43 while(L<=R)if(chk(L+R>>1,l))ans=L=L+R>>1,L++;else R=(L+R>>1)-1; 44 cout<<ans<<endl; 45 } 46 }
你的名字：
$Description:$
实力强大的小 A 被选为了 ION2018 的出题人，现在他需要解决题目的命名问题。
小 A 被选为了 ION2018 的出题人，他精心准备了一道质量十分高的题目，且已经把除了题目命名以外的工作都做好了。
由于 ION 已经举办了很多届，所以在题目命名上也是有规定的，ION 命题手册规定：每年由命题委员会规定一个小写字母字符串，我们称之为那一年的命名串，要求每道题的名字必须是那一年的命名串的一个非空连续子串，且不能和前一年的任何一道题目的名字相同。
由于一些特殊的原因，小 A 不知道 ION2017 每道题的名字，但是他通过一些特殊手段得到了 ION2017 的命名串，现在小 A 有Q次询问：每次给定 ION2017 的命名串和 ION2018 的命名串，求有几种题目的命名，使得这个名字一定满足命题委员会的规定，即是 ION2018 的命名串的一个非空连续子串且一定不会和 ION2017 的任何一道题目的名字相同。
由于一些特殊原因，所有询问给出的 ION2017 的命名串都是某个串的连续子串
对于$68%$的数据，ION的命名串是给出的那个整个串。
对于$100%$的数据，$sum |T| le 10^6,|S| le 5 imes 10^5,Q le 10^5$
题意：给定S，每次询问T的多少个子串不是S[l,r]的子串。
前$68$分还是可以自己想的。
一个$SAM$匹配，一个$SAM$统计，所有节点减去是子串的部分（匹配长度）就是答案。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define S 2222222 4 int len[2][S],f[2][S],c[2][26][S],pc=1,lst=1,n,mx[S],L,R;char s[S];vector<int>v[S]; 5 void insert(int C,int*len,int*f,int c[26][S],int&lst,int&pc,int M){ 6 int p=lst,np=lst=++pc,q,nq; len[np]=len[p]+1; mx[np]=M; 7 for(int i=0;i<26;++i)c[i][p]=0; 8 for(;p&&!c[C][p];p=f[p])c[C][p]=np; 9 if(!p){f[np]=1;return;}q=c[C][p]; 10 if(len[q]==len[p]+1){f[np]=q;return;} 11 len[nq=++pc]=len[p]+1; f[nq]=f[q]; f[q]=f[np]=nq; mx[nq]=0; 12 for(int i=0;i<26;++i)c[i][nq]=c[i][q]; 13 for(;c[C][p]==q;p=f[p])c[C][p]=nq; 14 } 15 int main(){//freopen("name.in","r",stdin);freopen("name.out","w",stdout); 16 scanf("%s%d",s,&n); 17 for(int i=0;s[i];++i)insert(s[i]-'a',len[0],f[0],c[0],lst,pc,0); 18 while(n--){ 19 scanf("%s%d%d",s,&L,&R); 20 int tlst=1,tpc=1,l=0;long long ans=0; 21 for(;s[l];++l);l--; 22 for(int j=0,p=1,m=0;j<=l;++j){ 23 while(!c[0][s[j]-'a'][p]&&p)p=f[0][p],m=len[0][p]; 24 p=c[0][s[j]-'a'][p];m++; 25 if(!p)p=1,m=0;insert(s[j]-'a',len[1],f[1],c[1],tlst,tpc,m); 26 }l++; 27 for(int j=2;j<=tpc;++j)v[len[1][j]].push_back(j); 28 for(int j=l;j;v[j].clear(),--j)for(int b=0;b<v[j].size();++b) 29 mx[f[1][v[j][b]]]=max(mx[f[1][v[j][b]]],mx[v[j][b]]); 30 for(int j=2;j<=tpc;++j)ans+=max(0,len[1][j]-max(len[1][f[1][j]],mx[j])); 31 printf("%lld ",ans); 32 } 33 }
然而我们考虑一下第一个SAM有什么用？其实用来匹配的只是找出边，跳父亲，查询$len$。
对于一个节点，它只要建出来了$len$就不会改变，所以区间的一个子串的$len$就是整个$SAM$的$len$
而父亲关系的改变只发生在复制$nq$的时候。而这样的话只要出边查的对跳两步也就能跳到了。
所以关键还是在于出边。可以发现，如果出边对应的点的endpos中含有l到r之间的数就可以了。
我们对每一个点动态开线段树，初始值为$firstpos$。然后每个点上传给父亲就是线段树合并。
需要及时开新点而不能直接改变原有的树（因为这棵树不一定是它自己的）
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define S 1999999 4 int len[2][S],f[2][S],c[2][26][S],pc=1,lst=1,n,mx[S],L,R,SL;char s[S];vector<int>v[S]; 5 int rt[S],lc[S<<5],rc[S<<5],PC=1;bool w[S<<5]; 6 #define md (cl+cr>>1) 7 void add(int&p,int v,int cl=1,int cr=SL){ 8 p=++PC; w[p]=1; if(cl==cr)return; 9 if(v<=md)add(lc[p],v,cl,md);else add(rc[p],v,md+1,cr); 10 } 11 int merge(int p,int tp){ 12 if(!(tp*p))return p|tp; 13 int x=++PC;lc[x]=merge(lc[p],lc[tp]);rc[x]=merge(rc[p],rc[tp]); 14 w[x]=w[lc[x]]|w[rc[x]]; return x; 15 } 16 int ask(int p,int l,int r,int cl=1,int cr=SL){ 17 if(r<l||!w[p])return 0; 18 if(l<=cl&&cr<=r)return 1; 19 if(l<=md&&ask(lc[p],l,r,cl,md))return 1; 20 return r>md&&ask(rc[p],l,r,md+1,cr); 21 } 22 void insert(int C,int*len,int*f,int c[26][S],int&lst,int&pc,int opt,int M){ 23 int p=lst,np=lst=++pc,q,nq; len[np]=len[p]+1; 24 if(opt)mx[np]=M;else add(rt[np],M); 25 for(int i=0;i<26;++i)c[i][p]=0; 26 for(;p&&!c[C][p];p=f[p])c[C][p]=np; 27 if(!p){f[np]=1;return;} q=c[C][p]; 28 if(len[q]==len[p]+1){f[np]=q;return;} 29 len[nq=++pc]=len[p]+1; f[nq]=f[q]; f[q]=f[np]=nq; 30 if(opt)mx[nq]=0;else rt[nq]=++PC; 31 for(int i=0;i<26;++i)c[i][nq]=c[i][q]; 32 for(;c[C][p]==q;p=f[p])c[C][p]=nq; 33 } 34 main(){ 35 scanf("%s%d",s,&n);rt[1]=1; SL=strlen(s); 36 for(int i=0;s[i];++i)insert(s[i]-'a',len[0],f[0],c[0],lst,pc,0,i+1); 37 for(int i=2;i<=pc;++i)v[len[0][i]].push_back(i); 38 for(int i=SL;i;v[i--].clear())for(int a=0;a<v[i].size();++a) 39 rt[f[0][v[i][a]]]=merge(rt[f[0][v[i][a]]],rt[v[i][a]]); 40 while(n--){ 41 scanf("%s%d%d",s,&L,&R); 42 int tlst=1,tpc=1,l=strlen(s)-1;long long ans=0; 43 for(int j=0,p=1,m=0;j<=l;++j){ 44 while(!ask(rt[c[0][s[j]-'a'][p]],L+m,R)&&p){m--;if(m<=len[0][f[0][p]])p=f[0][p];} 45 p=c[0][s[j]-'a'][p];m++; 46 if(!p)p=1,m=0;insert(s[j]-'a',len[1],f[1],c[1],tlst,tpc,1,m); 47 }l++; 48 for(int j=2;j<=tpc;++j)v[len[1][j]].push_back(j); 49 for(int j=l;j;v[j--].clear())for(int b=0;b<v[j].size();++b) 50 mx[f[1][v[j][b]]]=max(mx[f[1][v[j][b]]],mx[v[j][b]]); 51 for(int j=2;j<=tpc;++j)ans+=max(0,len[1][j]-max(len[1][f[1][j]],mx[j])); 52 printf("%lld ",ans); 53 } 54 }