题目描述
lovelive预赛要求原创歌曲，所以小海要准备新歌的词。小海有一段模板串ai,长度为n，她可以在模板串中选择一个区间的子串来作为歌词。但是已经有m个区间[li,ri]的子串被当做歌词了。为了保证原创，小海这次选出来的子串中不能出现之前给出的m个子串。小海想知道有多少可行的区间可以选择。
输入
第一行2个数 n,m
第二行一个字符串ai
接下来m行，每行两个数li,ri
输出
一个数表示答案
样例输入
6 2 aabaac 2 3 5 6
样例输出
10
提示
数据范围：
20% n,m<=100
另外20% ri-li<=10
另外 20% sigma ri-li<=n
另外0% 没有两个已被选出的子串互相包含
100% n,m<=3e5
考虑以$i$为结尾的串，合法的左端点都是一段连续的区间，形如$[l,i-1]$
令$f[i]=l$
那么考虑一段区间$[l,r]$，它会对所有包含他的后缀$b$的$f[b]$产生$b-(r-l+1)+1+1$的贡献。
注意贡献要取$max$，另外有$f[i]=max(f[i],f[i-1])$。
用后缀自动机来干这个事情就行了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define M 600010 4 #define LL long long 5 #define inf 1047483647 6 int tranc[M][27]; 7 int len[M], fa[M]; 8 int ri[M]; 9 int cnt = 1, tail = 1; 10 int c[M], od[M]; 11 int ft[M][20]; 12 int mn[M]; 13 int wh[M]; 14 struct Edge{ 15 int u, v, Next; 16 } G[M]; 17 int head[M], tot; 18 inline void add(int u, int v) { 19 G[++ tot] = (Edge){u, v, head[u]}; 20 head[u] = tot; 21 } 22 inline void insert(int k) { 23 int p = tail, np = ++ cnt, q, nq; 24 len[np] = len[p] + 1; 25 ri[np] = 1; 26 for(; p && !tranc[p][k]; p = fa[p]) { 27 tranc[p][k] = np; 28 } 29 if(!p) fa[np] = 1; 30 else { 31 q = tranc[p][k]; 32 if(len[q] == len[p] + 1) fa[np] = q; 33 else { 34 fa[nq = ++ cnt] = fa[q]; 35 memcpy(tranc[nq], tranc[q], sizeof(tranc[q])); 36 fa[q] = fa[np] = nq; 37 len[nq] = len[p] + 1; 38 for(; tranc[p][k] == q; p = fa[p]) { 39 tranc[p][k] = nq; 40 } 41 } 42 } 43 tail = np; 44 } 45 inline void init(int m) { 46 for(int i = 1; i <= cnt; ++ i) c[len[i]] ++, mn[i] = inf; 47 for(int i = 1; i <= m; ++ i) c[i] += c[i - 1]; 48 for(int i = cnt; i >= 1; -- i) od[c[len[i]] --] = i; 49 for(int i = cnt; i >= 1; -- i) { 50 ri[fa[od[i]]] += ri[od[i]]; 51 } 52 memset(head, -1, sizeof(head)); 53 for(int i = 2; i <= cnt; ++ i) { 54 add(fa[i], i); 55 ft[i][0] = fa[i]; 56 } 57 for(int i = 1; i <= 19; ++ i) { 58 for(int j = 1; j <= cnt; ++ j) { 59 ft[j][i] = ft[ft[j][i - 1]][i - 1]; 60 } 61 } 62 } 63 int L[M], R[M], id[M]; 64 int dfs_clock, f[M], h[M]; 65 inline void dfs(int x, int g) { 66 id[L[x] = ++ dfs_clock] = x; 67 int j = g; 68 if(mn[x] != inf) j = 1; 69 for(int i = head[x]; i != -1; i = G[i].Next) { 70 dfs(G[i].v, j); 71 } 72 R[x] = dfs_clock; 73 if(!g && j) { 74 for(int i = L[x]; i <= R[x]; ++ i) { 75 int b = h[id[i]]; 76 if(b) f[b] = max(f[b], b - mn[x] + 2); 77 } 78 } 79 } 80 char s[M]; 81 int main() { 82 int n, m; 83 scanf("%d%d", &n, &m); 84 scanf("%s", s + 1); 85 for(int i = 1; i <= n; ++ i) { 86 insert(s[i] - 'a'); 87 wh[i] = tail; 88 h[tail] = i; 89 } 90 init(cnt); 91 for(int i = 1; i <= m; ++ i) { 92 int l, r; 93 scanf("%d%d", &l, &r); 94 int o = wh[r]; 95 for(int j = 19; j >= 0; -- j) { 96 if(len[ft[o][j]] >= r - l + 1) { 97 o = ft[o][j]; 98 } 99 } 100 mn[o] = min(mn[o], r - l + 1); 101 } 102 for(int i = 1; i <= n; ++ i) f[i] = 1; 103 dfs(1, 0); 104 LL Ans = 0; 105 for(int i = 1; i <= n; ++ i) { 106 Ans += i - f[i] + 1; 107 f[i + 1] = max(f[i + 1], f[i]); 108 } 109 printf("%lld ", Ans); 110 }