Statement

给定字符串 ss，定义前缀 ii 表示 s[1:i]s[1:i]。mm 次询问，每次询问给出两个数 l,rl,r，求从前缀 l∼rl\sim r 中选出两个前缀的所有方案中，这两个前缀的最长公共后缀长度的最大值。

数据范围：∣s∣≤105|s|\le10^5，∣Σ∣≤2|\Sigma|\le2。

Solution

题目可以转化为后缀树上点集 SS 中选两个点的 LCA 的 maxlen\text{maxlen} 最大值，即 max⁡i∈S,j∈S,i≠j{maxlen(LCA(i,j))}\max\limits_{i\in S,j\in S,i\ne j}\{\text{maxlen}(\text{LCA}(i,j))\}。这就变成了一个纯树上数据结构问题。

离线询问，将询问按 rr 排序。需要支持的操作是加入一个点，求后缀 max⁡\max。可以看出我们打算在每个 ii 处维护所有 (i,j)(i,j) 满足 i<ji<j 的贡献。

观察到加入一个点只会多出一个 LCA。为了进一步分析，我们可以标出每个 LCA（假定为 xx）的贡献被统计到的 ii 是谁。下图中记这个 ii 为 QiQi。

上图 (a) 中展示了 1∼81\sim8 号点组成的点集的 QiQi 状况。考虑在不同位置加入 99 号点，分别如上图 (b) © (d) 所示。因为我们必须保持 xx 在所有 LCA(i,j)=x\text{LCA}(i,j)=x 的 (i,j)(i,j)（i<ji<j）对中，ii 最大处被统计到，所以不仅新增了 Q8Q8，还会有部分 QiQi 向下移动了。

或许下面这张图更好地说明了 QiQi 的移动方式：

上图中，新加入的 99 号点会使 Q2,Q6,Q7Q2,Q6,Q7 依次向下移动，最后在根节点产生 Q8Q8。

这个过程很容易让人想起 LCT 的 access 函数。加入一个点 rr，相当于给 rr 到根的路径覆盖上颜色 rr。

上图中，99 到根路径依次遇到了颜色 2,6,7,82,6,7,8。一个颜色就是一条重链，而这些重链的相交位置就是向下移动的 QiQi。

所以我们用一棵不用换根的 LCT 来维护每个 xx 对应的 QiQi，以及路径颜色覆盖。在 access 中 QiQi 下移时，我们使用树状数组来更新 ii 的贡献，并维护后缀 max⁡\max。

时间复杂度 O(nlog⁡2n)O(n\log^2n)，其中 n=∣s∣n=|s|。

Code

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
void pushdown(int x) {
    if(tag[x]){
        if (ch[x][0]) qi[ch[x][0]] = tag[ch[x][0]] = tag[x];
        if (ch[x][1]) qi[ch[x][1]] = tag[ch[x][1]] = tag[x];
        tag[x] = 0;
    }
}
void access(int x, int id) {
    int t;
    for (; x; x = fa[t = x]) splay(x), ch[x][1] = t, BIT::add(qi[x], len[x]);
    qi[t] = tag[t] = id;
}

完整代码

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
#include <bits/stdc++.h>
const int N = 2e5 + 7, M = 2;
namespace SAM {
int tr[N][M], fail[N], len[N], siz[N], pnodes = 1, last = 1;
void insert(int x) {
    int u = ++pnodes, p = last;
    len[u] = len[p] + 1, siz[u] = 1, last = u;
    while (p && !tr[p][x]) tr[p][x] = u, p = fail[p];
    if (!p) return fail[u] = 1, void();
    int q = tr[p][x];
    if (len[q] == len[p] + 1) return fail[u] = q, void();
    int cq = ++pnodes;
    memcpy(tr[cq], tr[q], sizeof tr[q]);
    len[cq] = len[p] + 1, fail[cq] = fail[q], fail[q] = fail[u] = cq;
    while (p && tr[p][x] == q) tr[p][x] = cq, p = fail[p];
}
}  // namespace SAM
namespace BIT {
int n, c[N];
void add(int x, int val) {
    while (x) c[x] = std::max(c[x], val), x -= x & -x;
}
int qmax(int x) {
    int s = 0;
    while (x <= n) s = std::max(s, c[x]), x += x & -x;
    return s;
}
}  // namespace BIT
namespace LCT {
struct Node* null;
struct Node {
    Node *pre, *son[2];
    int len, node, tag;
    bool get() { return pre->son[1] == this; }
    bool isRoot() { return pre->son[0] != this && pre->son[1] != this; }
    void connect(Node* s, bool id) {
        if (this != null) son[id] = s;
        if (s != null) s->pre = this;
    }
    void pushdown() {
        if (son[0] != null) son[0]->node = son[0]->tag = tag;
        if (son[1] != null) son[1]->node = son[1]->tag = tag;
        tag = 0;
    }
} pool[N];
void rotate(Node* x) {
    Node *y = x->pre, *z = y->pre;
    bool k = x->get(), kk = y->get(), t = y->isRoot();
    y->connect(x->son[k ^ 1], k), x->connect(y, k ^ 1);
    if (t)
        x->pre = z;
    else
        z->connect(x, kk);
}
void splay(Node* x) {
    static Node* stk[N];
    int pstk = 0;
    Node* y = x;
    stk[++pstk] = y;
    while (!y->isRoot()) stk[++pstk] = y = y->pre;
    while (pstk)
        if ((y = stk[pstk--])->tag) y->pushdown();
    while (!x->isRoot()) {
        if (!(y = x->pre)->isRoot()) rotate(x->get() == y->get() ? y : x);
        rotate(x);
    }
}
Node* getNode(int x) { return pool + x + 1; }
void init() {
    null = pool, *null = {null, {null, null}, 0, 0, 0};
    for (int i = 0; i <= SAM::pnodes; i++) {
        Node* x = getNode(i);
        *x = *null, x->len = SAM::len[i];
        if (i) x->pre = getNode(SAM::fail[i]);
    }
}
void access(int y, int id) {
    Node *x = getNode(y), *t = null;
    for (; x != null; x = (t = x)->pre) splay(x), x->son[1] = t, BIT::add(x->node, x->len);
    t->node = t->tag = id;
}
}  // namespace LCT
int n, m, pos[N], ans[N];
char s[N];
std::vector<std::pair<int, int>> que[N];
int main() {
    scanf("%d%d%s", &n, &m, s + 1);
    for (int i = 1; i <= n; i++) SAM::insert(s[i] - '0'), pos[i] = SAM::last;
    LCT::init(), BIT::n = n;
    for (int i = 1, l, r; i <= m; i++) scanf("%d%d", &l, &r), que[r].emplace_back(l, i);
    for (int r = 1; r <= n; r++) {
        LCT::access(pos[r], r);
        for (auto p : que[r]) ans[p.second] = BIT::qmax(p.first);
    }
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}