OI

BZOJ 3879: SvT

Description

(我并不想告诉你题目名字是什么鬼)

有一个长度为n的仅包含小写字母的字符串S,下标范围为[1,n].

现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在S中出现的起始位置来表示),求这些后缀两两之间的LCP(LongestCommonPrefix)的长度之和.一对后缀之间的LCP长度仅统计一遍.

Input

第一行两个正整数n,m,分别表示S的长度以及询问的次数.

接下来一行有一个字符串S.

接下来有m组询问,对于每一组询问,均按照以下格式在一行内给出:

首先是一个整数t,表示共有多少个后缀.接下来t个整数分别表示t个后缀在字符串S中的出现位置.

Output

对于每一组询问,输出一行一个整数,表示该组询问的答案.由于答案可能很大,仅需要输出这个答案对于23333333333333333(一个巨大的质数)取模的余数.

Sample Input

1
2
3
4
5

7 3
popoqqq
1 4
2 3 5
4 1 2 5 6

Sample Output

1
2
3

0
0
2

HINT

样例解释:

对于询问一,只有一个后缀”oqqq”,因此答案为0.

对于询问二,有两个后缀”poqqq”以及”qqq”,两个后缀之间的LCP为0,因此答案为0.

对于询问三,有四个后缀”popoqqq”,”opoqqq”,”qqq”,”qq”,其中只有”qqq”,”qq”两个后缀之间的LCP不为0,且长度为2,因此答案为2.

对于100%的测试数据,有S<=510^5,且Σt<=310^6.

特别注意:由于另一世界线的某些参数发生了变化,对于一组询问,即使一个后缀出现了多次,也仅算一次.

Source

By YGY

Solution

建立后缀数组，对输入按照rank排序，发现就是求 \( \sum_{1 \le L \le R \le n} \min{a_L … a_R} \)

利用单调栈求出每个height_i控制区间即可。

我想在这里讨论一种奇葩的做法：

首先求出来原串height，然后在height两两元素之间插入一个INF，首尾也要插入。

对于这个新建立的序列我们称为a，对a建立一个笛卡尔树。显然询问的点就是为INF的点。两个点答案就是他们的LCA。

对所有询问的后缀找出他们在树中位置，构建虚树。

考虑虚树中每个节点i对答案贡献：a[i] * i->lc->siz * i->rc->siz。

最后求一个和就好了。

这样做TLE了，不知道漏洞在哪。（常数？）

（这做法码了好久，RE + TLE，爽到！）

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1000005;
const LL P = 23333333333333333ll;
inline int getint() { int r = 0; bool b = true; char c = getchar(); while ('0' > c || c > '9') { if (c == '-') b = false; c = getchar(); } while ('0' <= c && c <= '9') { r = (r << 3) + (r << 1) + (c - '0'); c = getchar(); } if (b) return r; return -r; }
int sta[maxn], tail, wa[maxn], wb[maxn], wc[maxn], a[maxn*3], n, m, q, rnk[maxn], sa[maxn], height[maxn], T[maxn], st[maxn][30];
char s[maxn];
LL ans;
void da() {
    int p, i, j, k, u, v, *x = wa, *y = wb, *z, *c = wc;
    for (i = 1; i <= m; ++i) c[i] = 0;
    for (i = 1; i <= n; ++i) c[x[i] = s[i]]++;
    for (i = 1; i <= m; ++i) c[i] += c[i - 1];
    for (i = n; i >= 1; --i) sa[c[x[i]]--] = i;
    for (j = 1; j < n; j <<= 1) {
        p = 0;
        for (i = n - j + 1; i <= n; ++i) y[++p] = i;
        for (i = 1; i <= n; ++i) if (sa[i] > j) y[++p] = sa[i] - j;
        for (i = 1; i <= m; ++i) c[i] = 0;
        for (i = 1; i <= n; ++i) c[x[y[i]]]++;
        for (i = 1; i <= m; ++i) c[i] += c[i - 1];
        for (i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i];
        y[v = sa[1]] = m = 1;
        for (i = 2; i <= n; ++i) {
            u = sa[i];
            if (x[u] != x[v] || x[u + j] != x[v + j]) ++m;
            y[v = u] = m;
        }
        z = x; x = y; y = z;
    }
    for (i = 1; i <= n; ++i) rnk[sa[i]] = i;
    p = 0;
    for (i = 1; i <= n; ++i) {
        p = max(p - 1, 0);
        if (rnk[i] == 1) continue;
        j = sa[rnk[i] - 1];
        while (i + p <= n && j + p <= n && s[i + p] == s[j + p]) ++p;
        height[rnk[i]] = p;
    }
}
inline int lcp(int x, int y) {
    int k = T[y-x+1];
    return min(st[x][k], st[y-(1<<k)+1][k]);
}
int main() {
    register int now;
    n = getint(); q = getint();
    scanf("%s", s + 1);
    m = 500; da(); T[0] = -1;
    for (int i = 1; i <= n; ++i) { st[i][0] = height[i]; T[i] = T[i>>1] + 1; }
    for (int k = 1; (1<<k) <= n; ++k)
        for (int i = 1; i <= n; ++i) st[i][k] = min(st[i][k-1], st[i+(1<<(k-1))][k-1]);
    while (q--) {
        m = getint(); tail = 0;
        for (int i = 1; i <= m; ++i) a[i] = rnk[getint()];
        sort(a + 1, a + m + 1);
        m = unique(a + 1, a + m + 1) - (a + 1);
        for (int i = 1; i < m; ++i) a[i] = lcp(a[i]+1, a[i+1]); a[m] = -1;
        for (int i = 1; i <= m; ++i) {
            while (tail > 0 && a[sta[tail]] >= a[i]) {
                now = sta[tail--];
                ans = (ans + LL(a[now]) * LL(now-sta[tail]) % P * LL(i-now) % P) % P;
            }
            sta[++tail] = i;
        }
        printf("%lld\n", ans);
        ans = 0ll;
    }
}

第二种方法（TLE）

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 2000005;
inline int getint() { int r = 0; bool b = true; char c = getchar(); while ('0' > c || c > '9') { if (c == '-') b = false; c = getchar(); } while ('0' <= c && c <= '9') { r = (r << 3) + (r << 1) + (c - '0'); c = getchar(); } if (b) return r; return -r; }
int siz[maxn], T[maxn], vis[maxn], x, pos[maxn], a[maxn], b[maxn * 3], sta[maxn], tail, cnt[maxn], dst[maxn], tot, n, m, wa[maxn], wb[maxn], rnk[maxn], sa[maxn], height[maxn], wc[maxn], clo, dfn[maxn], fa[maxn], dfm[maxn], c[maxn][2], tid[maxn];
char s[maxn];
LL ans;
pair<int, int> st[maxn][21];
void dfs(int now) {
    if (now == 0) return;
    dfn[now] = ++clo;
    tid[clo] = now;
    dfs(c[now][0]);
    dfs(c[now][1]);
    dfm[now] = clo;
}
inline int lca(int x, int y) {
    if (y<x) swap(x, y);
    int k = T[y-x+1];
    return min(st[x][k], st[y-(1<<k)+1][k]).second;
}
void ins(int x, int y) { c[x][cnt[x]++] = y; }
void da() {
    int p, i, j, k, u, v, *x = wa, *y = wb, *z, *c = wc;
    for (i = 1; i <= m; ++i) c[i] = 0;
    for (i = 1; i <= n; ++i) c[x[i] = s[i]]++;
    for (i = 1; i <= m; ++i) c[i] += c[i - 1];
    for (i = n; i >= 1; --i) sa[c[x[i]]--] = i;
    for (j = 1; j < n; j <<= 1) {
        p = 0;
        for (i = n - j + 1; i <= n; ++i) y[++p] = i;
        for (i = 1; i <= n; ++i) if (sa[i] > j) y[++p] = sa[i] - j;
        for (i = 1; i <= m; ++i) c[i] = 0;
        for (i = 1; i <= n; ++i) c[x[y[i]]]++;
        for (i = 1; i <= m; ++i) c[i] += c[i - 1];
        for (i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i];
        y[v = sa[1]] = m = 1;
        for (i = 2; i <= n; ++i) {
            u = sa[i];
            if (x[u] != x[v] || x[u + j] != x[v + j]) ++m;
            y[v = u] = m;
        }
        z = x; x = y; y = z;
    }
    for (i = 1; i <= n; ++i) rnk[sa[i]] = i;
    p = 0;
    for (i = 1; i <= n; ++i) {
        p = max(p - 1, 0);
        if (rnk[i] == 1) continue;
        j = sa[rnk[i] - 1];
        while (i + p <= n && j + p <= n && s[i + p] == s[j + p]) ++p;
        height[rnk[i]] = p;
    }
}
const LL P = 23333333333333333ll;
void dfs2(int now) {
    if (now == 0) return;
    siz[now] = (vis[now] == clo);
    for (int i = 0; i < cnt[now]; ++i) {
        dfs2(c[now][i]);
        siz[now] += siz[c[now][i]];
    }
    if (cnt[now] == 2) ans = (ans + LL(a[now]) * LL(siz[c[now][0]]) % P * LL(siz[c[now][1]]) % P) % P;
}
int main() {
    int lst, rt, q, l;
    n = getint(); q = getint();
    scanf("%s", s + 1);
    m = 500; da();
    a[tot = 1] = n;
    pos[1] = tot;
    for (int i = 2; i <= n; ++i) {
        a[++tot] = height[i];
        a[++tot] = n;
        pos[i] = tot;
    }
    T[0]=-1;
    for (int i = 1; i <= tot; ++i) {
        T[i]=T[i>>1]+1;
        lst = 0;
        if (tail > 0 && a[i] < a[sta[tail]])
            while (true) {
                lst = sta[tail--];
                if (tail > 0 && a[i] < a[sta[tail]]) {
                    fa[lst] = sta[tail];
                    c[sta[tail]][1] = lst;
                }
                else break;
            }
        fa[i] = sta[tail];
        c[i][0] = lst;
        fa[lst] = i;
        sta[++tail] = i;
    }
    while (tail > 1) {
        lst = sta[tail--];
        c[sta[tail]][1] = lst;
        fa[lst] = sta[tail];
    }
    rt = sta[1];
    dfs(rt); dfn[0] = 1; dfm[0] = tot;
    clo = 0;
    for (int i = 1; i <= tot; ++i) st[i][0] = make_pair(a[i], i);
    for (int k = 1; (1 << k) <= tot; ++k)
        for (int i = 1; i <= tot; ++i)
            st[i][k] = min(st[i][k-1], st[i+(1<<(k-1))][k-1]);
    while (q--) {
        ++clo;
        m = getint();
        for (int i = 1; i <= m; ++i) {
            x = getint();
            b[i] = dfn[pos[rnk[x]]];
            vis[pos[rnk[x]]] = clo;
        }
        sort(b + 1, b + m + 1);
        m = unique(b + 1, b + m + 1) - (b + 1);
        tail = 0;
        for (int i = 1; i <= m; ++i) {
            if (dfn[sta[tail]] <= b[i] && b[i] <= dfm[sta[tail]]) sta[++tail] = tid[b[i]];
            else {
                while (b[i] < dfn[sta[tail]] || b[i] > dfm[sta[tail]]) {
                    lst = sta[tail--];
                    if (dfn[sta[tail]] <= b[i] && b[i] <= dfm[sta[tail]]) break;
                    else {
                        ins(sta[tail], lst);
                        dst[++tot] = sta[tail];
                    }
                }
                l = lca(tid[b[i]], lst);
                ins(l, lst);
                dst[++tot] = l;
                sta[++tail] = l;
                sta[++tail] = tid[b[i]];
            }
        }
        while (tail > 1) {
            lst = sta[tail--];
            ins(sta[tail], lst);
            dst[++tot] = sta[tail];
        }
        rt = sta[1];
        ans = 0ll;
        dfs2(rt);
        printf("%lld\n", ans);
        for (int i = 1; i <= tot; ++i) cnt[dst[i]] = 0;
        tot = 0;
    }
}