把sa求出来之后， 对于每个询问用单调栈处理。
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = (int)2e5 + 7; const int LOG = 18; namespace SA { int sa[N], rk[N], ht[N], s[N<<1], t[N<<1], p[N], cnt[N], cur[N]; #define pushS(x) sa[cur[s[x]]--] = x #define pushL(x) sa[cur[s[x]]++] = x #define inducedSort(v) fill_n(sa, n, -1); fill_n(cnt, m, 0); for (int i = 0; i < n; i++) cnt[s[i]]++; for (int i = 1; i < m; i++) cnt[i] += cnt[i-1]; for (int i = 0; i < m; i++) cur[i] = cnt[i]-1; for (int i = n1-1; ~i; i--) pushS(v[i]); for (int i = 1; i < m; i++) cur[i] = cnt[i-1]; for (int i = 0; i < n; i++) if (sa[i] > 0 && t[sa[i]-1]) pushL(sa[i]-1); for (int i = 0; i < m; i++) cur[i] = cnt[i]-1; for (int i = n-1; ~i; i--) if (sa[i] > 0 && !t[sa[i]-1]) pushS(sa[i]-1); void sais(int n, int m, int *s, int *t, int *p) { int n1 = t[n-1] = 0, ch = rk[0] = -1, *s1 = s+n; for (int i = n-2; ~i; i--) t[i] = s[i] == s[i+1] ? t[i+1] : s[i] > s[i+1]; for (int i = 1; i < n; i++) rk[i] = t[i-1] && !t[i] ? (p[n1] = i, n1++) : -1; inducedSort(p); for (int i = 0, x, y; i < n; i++) if (~(x = rk[sa[i]])) { if (ch < 1 || p[x+1] - p[x] != p[y+1] - p[y]) ch++; else for (int j = p[x], k = p[y]; j <= p[x+1]; j++, k++) if ((s[j]<<1|t[j]) != (s[k]<<1|t[k])) {ch++; break;} s1[y = x] = ch; } if (ch+1 < n1) sais(n1, ch+1, s1, t+n, p+n1); else for (int i = 0; i < n1; i++) sa[s1[i]] = i; for (int i = 0; i < n1; i++) s1[i] = p[sa[i]]; inducedSort(s1); } template<typename T> int mapCharToInt(int n, const T *str) { int m = *max_element(str, str+n); fill_n(rk, m+1, 0); for (int i = 0; i < n; i++) rk[str[i]] = 1; for (int i = 0; i < m; i++) rk[i+1] += rk[i]; for (int i = 0; i < n; i++) s[i] = rk[str[i]] - 1; return rk[m]; } // Ensure that str[n] is the unique lexicographically smallest character in str. template<typename T> void suffixArray(int n, const T *str) { int m = mapCharToInt(++n, str); sais(n, m, s, t, p); for (int i = 0; i < n; i++) rk[sa[i]] = i; for (int i = 0, h = ht[0] = 0; i < n-1; i++) { int j = sa[rk[i]-1]; while (i+h < n && j+h < n && s[i+h] == s[j+h]) h++; if (ht[rk[i]] = h) h--; } } }; using SA::sa; using SA::rk; using SA::ht; int n, q; char s[N]; int rmq[N][LOG], Log[N]; int a[N], b[N]; int v[N], c[N]; inline int getLcp(int x, int y) { if(x == y) return n - sa[x]; x++; int k = Log[y - x + 1]; return min(rmq[x][k], rmq[y - (1 << k) + 1][k]); } int main() { for(int i = 2; i < N; i++) Log[i] = Log[i >> 1] + 1; scanf("%d%d", &n, &q); scanf("%s", s); SA::suffixArray(n, s); for(int i = 1; i <= n; i++) rmq[i][0] = ht[i]; for(int j = 1; j <= Log[n]; j++) { for(int i = 1; i + (1 << j) - 1 <= n; i++) { rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << j - 1)][j - 1]); } } while(q--) { LL ans = 0, now; int k, l, a_tot = 0, b_tot = 0, top; scanf("%d%d", &k, &l); for(int i = 1; i <= k; i++) { int x; scanf("%d", &x); x--; a[++a_tot] = rk[x]; } for(int i = 1; i <= l; i++) { int x; scanf("%d", &x); x--; b[++b_tot] = rk[x]; } sort(a + 1, a + 1 + a_tot); sort(b + 1, b + 1 + b_tot); top = now = 0; for(int i = 1, j = 1; i <= a_tot; i++) { while(j <= b_tot && b[j] <= a[i]) { int lcp, cnt; if(top) { lcp = getLcp(b[j - 1], b[j]); cnt = 0; while(top && v[top] >= lcp) { now -= 1LL * v[top] * c[top], cnt += c[top], top--; } if(cnt) { v[++top] = lcp; c[top] = cnt; now += 1LL * lcp * cnt; } } v[++top] = n - sa[b[j]]; c[top] = 1; now += n - sa[b[j]]; j++; } if(top) { int lcp = getLcp(b[j - 1], a[i]), cnt = 0; while(top && v[top] >= lcp) now -= 1LL * v[top] * c[top], cnt += c[top], top--; if(cnt) { v[++top] = lcp; c[top] = cnt; now += 1LL * lcp * cnt; } } ans += now; } top = now = 0; for(int i = a_tot, j = b_tot; i >= 1; i--) { while(j >= 1 && b[j] > a[i]) { int lcp, cnt; if(top) { lcp = getLcp(b[j], b[j + 1]); cnt = 0; while(top && v[top] >= lcp) now -= 1LL * v[top] * c[top], cnt += c[top], top--; if(cnt) { v[++top] = lcp; c[top] = cnt; now += 1LL * lcp * cnt; } } v[++top] = n - sa[b[j]]; c[top] = 1; now += n - sa[b[j]]; j--; } if(top) { int lcp = getLcp(a[i], b[j + 1]), cnt = 0; while(top && v[top] >= lcp) now -= 1LL * v[top] * c[top], cnt += c[top], top--; if(cnt) { v[++top] = lcp; c[top] = cnt; now += 1LL * lcp * cnt; } } ans += now; } printf("%lld ", ans); } return 0; } /* */