这题TM是计数神题......SAM就是个板子，别脑残写错就完事了。有个技巧是快速定位子串，倍增即可。
考虑反着来，就是两个断点切割所有串，求方案数。
大概分类讨论一下......先特判掉一些情况。然后考虑最左右的两个串是否相交。
相交的情况比较友善，先特殊统计有断点在交集中。之后枚举第一个断点切割了1 ~ i个串。第二个断点就切割i+1 ~ m个串。
然后写出一个∑的式子，拆开之后发现维护right集合平方和和right集合相邻元素的乘积即可。
不相交的麻烦点(极其麻烦...)考虑枚举第一个断点切割了1~i个串，这里的i的限制是L ~ R，可以先求出来。
然后继续化简一个∑式子，最后发现要维护的东西差不多。于是这题做完了。
感想：对拍真好用.jpg
#include <bits/stdc++.h> typedef long long LL;
const int N = , M = ; struct Edge {
int nex, v;
}edge[N]; int tp; int tr[N][], fail[N], len[N], rt[N], last = , tot = ;
int ls[M], rs[M], cnt, e[N], ed[N], fa[N][], pw[N];
LL sum0[M], sum2[M], sumd[M], large[M], small[M];
int n, q;
char str[N]; inline void add(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
} inline void pushup(int o) {
if(!ls[o] && !rs[o]) return;
sum0[o] = sum0[ls[o]] + sum0[rs[o]];
sum2[o] = sum2[ls[o]] + sum2[rs[o]];
sumd[o] = sumd[ls[o]] + sumd[rs[o]];
if(ls[o] && rs[o]) sumd[o] += small[rs[o]] * large[ls[o]];
large[o] = std::max(large[ls[o]], large[rs[o]]);
small[o] = std::min(small[ls[o]], small[rs[o]]);
return;
} int merge(int x, int y) {
if(!x || !y) return x | y;
int o = ++cnt;
large[o] = large[x];
small[o] = small[x];
sum0[o] = sum0[x];
sum2[o] = sum2[x];
sumd[o] = sumd[x];
ls[o] = merge(ls[x], ls[y]);
rs[o] = merge(rs[x] ,rs[y]);
pushup(o);
return o;
} void insert(int p, int l, int r, int &o) {
if(!o) o = ++cnt;
if(l == r) {
large[o] = small[o] = r;
sum0[o] = ;
sum2[o] = 1ll * r * r;
sumd[o] = ;
return;
}
int mid = (l + r) >> ;
if(p <= mid) insert(p, l, mid, ls[o]);
else insert(p, mid + , r, rs[o]);
pushup(o);
return;
} inline void insert(char c, int id) {
int f = c - '', p = last, np = ++tot;
last = np;
insert(id, , n, rt[np]);
len[np] = len[p] + ;
while(p && !tr[p][f]) {
tr[p][f] = np;
p = fail[p];
}
if(!p) {
fail[np] = ;
}
else {
int Q = tr[p][f];
if(len[Q] == len[p] + ) {
fail[np] = Q;
}
else {
int nQ = ++tot;
len[nQ] = len[p] + ;
fail[nQ] = fail[Q];
fail[Q] = fail[np] = nQ;
memcpy(tr[nQ], tr[Q], sizeof(tr[Q]));
while(tr[p][f] == Q) {
tr[p][f] = nQ;
p = fail[p];
}
}
}
return;
} int ask0(int L, int R, int l, int r, int o) {
if(!o) return ;
if(L <= l && r <= R) return sum0[o];
int mid = (l + r) >> , ans = ;
if(L <= mid) ans += ask0(L, R, l, mid, ls[o]);
if(mid < R) ans += ask0(L, R, mid + , r, rs[o]);
return ans;
} LL ask2(int L, int R, int l, int r, int o) {
if(!o) return ;
if(L <= l && r <= R) return sum2[o];
int mid = (l + r) >> ;
LL ans = ;
if(L <= mid) ans += ask2(L, R, l, mid, ls[o]);
if(mid < R) ans += ask2(L, R, mid + , r, rs[o]);
return ans;
} LL askd(int L, int R, int l, int r, int o) {
if(!o) return ;
if(L <= l && r <= R) return sumd[o];
int mid = (l + r) >> ;
if(R <= mid) return askd(L, R, l, mid, ls[o]);
if(mid < L) return askd(L, R, mid + , r, rs[o]);
LL ans = askd(L, R, l, mid, ls[o]) + askd(L, R, mid + , r, rs[o]);
if(ls[o] && rs[o]) {
ans += large[ls[o]] * small[rs[o]];
}
return ans;
} int getKpos(int k, int l, int r, int o) {
if(l == r) return r;
int mid = (l + r) >> ;
if(k <= sum0[ls[o]]) return getKpos(k, l, mid, ls[o]);
else return getKpos(k - sum0[ls[o]], mid + , r, rs[o]);
} void DFS(int x) {
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
fa[y][] = x;
DFS(y);
rt[x] = merge(rt[x], rt[y]);
}
return;
} inline void prework() {
for(int i = ; i <= tot; i++) pw[i] = pw[i >> ] + ;
for(int j = ; j <= pw[tot]; j++) {
for(int i = ; i <= tot; i++) {
fa[i][j] = fa[fa[i][j - ]][j - ];
}
}
return;
} inline int getPos(int x, int Len) {
int t = pw[tot];
while(t >= && len[fa[x][]] >= Len) {
if(len[fa[x][t]] >= Len) {
x = fa[x][t];
}
t--;
}
return x;
} inline LL getAns(int Len, int root) { if(Len == ) return ; int r1 = small[root], rn = large[root];
int l1 = r1 - Len + , ln = rn - Len + ; if(ask0(r1 + Len - , ln, , n, root)) {
return ;
}
LL ans = ;
if(r1 > ln) { /// cross
ans = sum2[root] - sumd[root] - 1ll * r1 * rn;
LL temp = (r1 - ln);
ans += (temp - ) * temp / + temp * (n - temp - );
}
else {
int ql = ask0(, r1 + Len - , , n, root), qr = ask0(, ln, , n, root);
int L = qr, R = ql;
int rL = getKpos(L, , n, root), rR = getKpos(R, , n, root), nexr = getKpos(R + , , n, root);
ans = 1ll * (r1 - rR + Len - ) * (nexr - ln) + 1ll * rL * ln - 1ll * rR * ln;
ans += ask2(rL + , rR, , n, root) - askd(rL, rR, , n, root);
}
return ans;
} int main() {
memset(small, 0x3f, sizeof(small));
scanf("%d%d", &n, &q);
scanf("%s", str + );
for(int i = ; i <= n; i++) {
insert(str[i], i);
}
int p = ;
for(int i = ; i <= n; i++) {
int f = str[i] - '';
p = tr[p][f];
ed[i] = p;
//printf("i = %d p = %d \n", i, p);
}
for(int i = ; i <= tot; i++) add(fail[i], i);
DFS();
prework();
LL SUM = 1ll * (n - ) * (n - ) / ;
for(int i = , l, r; i <= q; i++) {
scanf("%d%d", &l, &r);
LL t = getAns(r - l + , rt[getPos(ed[r], r - l + )]);
printf("%lld\n", SUM - t);
}
return ;
}
AC代码