【题解】CF-GYM-Deep Purple

Posted on Edited on In Disqus:

题目

2015-2016 Petrozavodsk Winter Training Camp, Moscow SU Trinity Contest

题意

给一个字符串 \(s\)，对于每一个 \([l, r]\) 的询问，求最大的 \(k(k\leqslant r-l)\) 使得 \(s[l\cdots l+k] = s[r-k \cdots r]=t\)。

题解

解法 1

  • 建立后缀树。
  • 对于一个询问 \([l, r]\)，\(t\) 一定在 \(s[1\cdots r]\) 对应的结点到根的路径上，如果能找到最大的小于 \(r\) 的 \(p\)（\(p\) 是某个前缀的对应结点），使得 \(p\) 和 \(t\) 的 LCA 对应的长度大于等于 \(p - l+1\)，于是便找到了这个询问的答案 \(k=p-l+1\)。
  • 具体实现：
    • 对后缀树树链剖分。
    • 按询问右端点排序，\(p\) 从 \(s\) 末尾向开头扫，如果 \(p\) 恰好是一个询问的右端点，那么插入这个询问。然后看 \(p\) 能完成哪些询问，完成后删除这些询问。
    • 插入：将 \(r\) 到根的链分成若干条子链，在每条子链的深度最大的对应的位置插入这个询问，值是 \(len(x)+l\)，维护区间最大值和对应的询问编号。
    • 询问：查询 \(p\) 到根的链上的最大询问，如果 \(len(x)+l>p\)，那么可以完成这个询问，直到不符合这个条件为止。
    • 坑：子链中的末端的那条不一定是完整的链，那么 \(len(x)\) 可能会受到 \(p\) 的限制（\(LCA(p,r)=p\)，\(r\) 在 \(p\) 子树中），也可能受到 \(r\) 的限制（其他情况），所以开了两个线段树分别考虑这两种情况。

这是 CF 上的某一份代码（链接 需要 Coach Mode 才能查看），可读性极佳：

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
#include <cstdio>
#include <cstring>
#include <set>
#include <queue>
#include <vector>

typedef std::pair<int, int> Info;

const int N = 400000 + 10;

int next[N][26], pre[N], len[N], tot = 1;

int append(int p, int c) {
    int np = ++tot;
    len[np] = len[p] + 1;
    for (; p && !next[p][c]; p = pre[p]) next[p][c] = np;
    if (!p) {
        pre[np] = 1;
    } else {
        int q = next[p][c];
        if (len[q] == len[p] + 1) {
            pre[np] = q;
        } else {
            int nq = ++tot;
            memcpy(next[nq], next[q], sizeof next[q]);
            len[nq] = len[p] + 1;
            pre[nq] = pre[q];
            pre[q] = pre[np] = nq;
            for (; p && next[p][c] == q; p = pre[p]) next[p][c] = nq;
        }
    }
    return np;
}

std::vector<int> adj[N];

int n, m, id[N];

char s[N];

int dep[N], size[N], son[N], top[N], left[N], right[N], bfn[N];
int *const fa = pre;

void bfs() {
    static int q[N];
    q[1] = dep[1] = 1;
    for (int i = 1, r = 1; i <= r; ++i) {
        int a = q[i];
        for (int j = 0; j < adj[a].size(); ++j) {
            int b = adj[a][j];
            dep[q[++r] = b] = dep[a] + 1;
        }
    }
    for (int i = 1; i <= tot; ++i) size[i] = 1;
    for (int i = tot; i > 1; --i) size[fa[q[i]]] += size[q[i]];
    for (int i = 2; i <= tot; ++i) if (size[son[fa[i]]] < size[i]) son[fa[i]] = i;
    for (int i = 1, cnt = 0; i <= tot; ++i) {
        int a = q[i];
        if (left[a]) continue;
        for (int b = a; b; b = son[b]) bfn[left[b] = ++cnt] = b, top[b] = a;
        for (int b = a; b; b = son[b]) right[b] = cnt;
    }
}

class Seg {
    inline int pos(int l, int r) { return (l + r) | (l != r); }

    std::set<Info> heap[N];
    Info max[2 * N];
public:
    void modify(int l, int r, int p) {
        int id = pos(l, r);
        if (l == r) {
            max[id] = (heap[p].empty() ? Info(0, 0) : *heap[p].rbegin());
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) modify(l, mid, p); else modify(mid + 1, r, p);
        max[id] = std::max(max[pos(l, mid)], max[pos(mid + 1, r)]);
    }

    void modify(int p, const Info &v, bool flag) {
        if (flag) heap[p].erase(v); else heap[p].insert(v);
        modify(1, tot, p);
    }

    Info query(int l, int r, int p, int q) {
        int id = pos(l, r);
        if (p <= l && r <= q) return max[id];
        int mid = (l + r) >> 1;
        Info res(0, 0);
        if (p <= mid) res = query(l, mid, p, q);
        if (q > mid) res = std::max(res, query(mid + 1, r, p, q));
        return res;
    }
} seg[2];

Info query(int p) {
    Info res(0, 0);
    for (; p; p = fa[top[p]]) {
        Info info = seg[1].query(1, tot, left[top[p]], left[p]);
        res = std::max(res, info);
        info = seg[0].query(1, tot, left[p], right[p]);
        info.first += len[p];
        res = std::max(res, info);
    }
    return res;
}

void modify(int p, const Info &v, bool flag = false) {
    for (; p; p = fa[top[p]]) {
        seg[0].modify(left[p], v, flag);
        Info info = v;
        info.first += len[p];
        seg[1].modify(left[p], info, flag);
    }
}

struct {
    int l, r;
} q[N];

int ans[N];

int main() {
    scanf("%d%d %s", &n, &m, s + 1);
    id[0] = 1;
    for (int i = 1; i <= n; ++i) id[i] = append(id[i - 1], s[i] - 'a');
    for (int i = 2; i <= tot; ++i) adj[pre[i]].push_back(i);
    bfs();
    static std::vector<int> event[N];
    for (int i = 1; i <= m; ++i) scanf("%d%d", &q[i].l, &q[i].r), event[q[i].r].push_back(i);
    for (int i = n; i > 0; --i) {
        do {
            Info info = query(id[i]);
            if (info.first <= i) break;
            int j = info.second;
            if (!ans[j]) ans[j] = i - q[j].l + 1;
            modify(id[q[j].r], Info(q[j].l, j), true);
        } while (1);
        for (int j = 0; j < event[i].size(); ++j) {
            int k = event[i][j];
            modify(id[i], Info(q[k].l, k));
        }
    }
    for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
    return 0;
}

解法 2

  • 见叉姐的《循环循环循》
  • 这题不补了。