P5576 题解 / 「永夜归返 -子时一刻-」

· · 题解

为官方题解的第二种方法的较详细版本。

离线询问，使用扫描线处理询问。

先对于所有 01 串建立广义后缀自动机，对于广义后缀自动机上的每一个节点，维护 l,r 表示它在 s_l, s_{l+1}, \cdots, s_r 中都出现过，如果有多个 [l,r]，优先取 r 最大的，其次取 r-l+1 最大的。

那么对于所有 R=i 的询问，我们可以在广义后缀自动机上找到所有维护信息形如 [l,i] 的节点 x（即：x 表示的 endpos 等价类是 s_i 的子串），对于所有 l\le L\le i 的左端点更新答案 ans_L\gets \max(ans_L,\operatorname{len}_x)。注意，当我们扫描线指针移动到一个新的 R 的时候，必须清空 ans 数组。

引理：

设 \operatorname{siz}_x 表示包含广义自动机上节点 x 的字符串个数（这里的字符串指的是原串），则 \sum\operatorname{siz}_x 是 \sum\operatorname{len}\times \sqrt{\sum\operatorname{len}} 级别的。

所以，我们需要做 \sum\operatorname{len}\times \sqrt{\sum\operatorname{len}} 区间修改操作，以及 m 次单点查询操作。

差分转化为单点修改，区间查询，然后使用分块根号平衡。
实现小技巧：如何在广义后缀自动机上找到所有 s 的子串？在 s 的前缀节点上跳 \operatorname{link} 树即可。

时间复杂度：\mathcal{O}(\sum\operatorname{len}\times \sqrt{\sum\operatorname{len}}+m\sqrt{n})。
不过没有体会到官方题解说的卡常，因为我没卡就是最优解。

#include <bits/stdc++.h>
using namespace std;
#define _rep(i_,a_,b_) for(int i_ = (a_); i_ <= (b_); ++i_)
#define mid ((L+R) >> 1)
#define multiCase() int testCnt = in(); _rep(curCase,1,testCnt)
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
using ll = long long;
using pii = pair<int,int>;

int in(void) { int x; scanf("%d", &x); return x; } ll inl(void) { ll x; scanf("%lld", &x); return x; }
void out(int x) { printf("%d ", x); } void outln(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld ", x); } void outln(ll x) { printf("%lld\n", x); }
template<typename T> void chkmax(T &a, const T &b) { a = max(a, b); } 
template<typename T> void chkmin(T &a, const T &b) { a = min(a, b); } 
const int kM = 805000;
int n, m;
string s[25000];
struct Query { int l, r, id; } q[kM]; int res[kM];

//general suffix automaton
int ch[kM][2], link[kM], len[kM], l[kM], r[kM], nc, vis[kM];
int clone(int x) { 
    ++nc; memcpy(ch[nc], ch[x], sizeof(ch[nc]));
    link[nc] = link[x], l[nc] = l[x], r[nc] = r[x];
    return nc;
}
int extend(int last, int c) { c -= '0';
    if(ch[last][c]) {
        int p = ch[last][c];
        if(len[p] == len[last] + 1) return p;
        else {
            int q = clone(p); len[q] = len[last] + 1;
            while(~last && ch[last][c] == p) ch[last][c] = q, last = link[last];
            link[p] = q; return q;
        }
    }
    int cur = ++nc; len[cur] = len[last] + 1; 
    while(~last && !ch[last][c]) ch[last][c] = cur, last = link[last];
    if(last == -1) link[cur] = 0;
    else {
        int p = ch[last][c];
        if(len[p] == len[last] + 1) link[cur] = p;
        else {
            int q = clone(p); len[q] = len[last] + 1;
            while(~last && ch[last][c] == p) ch[last][c] = q, last = link[last];
            link[p] = link[cur] = q;
        }   
    }
    return cur;
}

int single[25000], bkmx[25000]; const int bk = 200;
void update(int pos, int x) {
    chkmax(single[pos], x);
    chkmax(bkmx[(pos - 1) / bk + 1], x);
} 
int query(int r) {
    int res = 0;
    for(int i = 1; i < (r - 1) / bk + 1; ++i) chkmax(res, bkmx[i]);
    for(int i = (r - 1) / bk * bk + 1; i <= r; ++i) chkmax(res, single[i]);
    return res;
}
void reset(int pos) { single[pos] = 0, bkmx[(pos - 1) / bk + 1] = 0; }

int main() {
    link[0] = -1; memset(r, -1, sizeof(r));
    ios::sync_with_stdio(false);
    cin >> n >> m;
    _rep(i,1,n) cin >> s[i];
    _rep(i,1,m) { cin >> q[i].l >> q[i].r; q[i].id = i; }
    sort(q + 1, q + 1 + m, [](const Query &a, const Query &b) -> int {
        return a.r < b.r;
    });
    int p = 0;
    _rep(i,1,n) {
        // debug("init r = %d\n", i);
        int cur = 0;
        vector<int> prefixNode, resume;
        for(auto &c : s[i]) cur = extend(cur, c), prefixNode.push_back(cur);
        for(auto &x : prefixNode) {
            while(~x && vis[x] < i) {
                vis[x] = i;
                if(r[x] == i - 1) ++r[x];
                else l[x] = i, r[x] = i;
                update(l[x], len[x]);
                // if(i == 8109) debug("Update [%d, %d] len %d\n", l[x], i - 1, len[x]);
                resume.push_back(l[x]);
                x = link[x];
            }
        }
        // if(i >= 8000 && i <= 8109) debug("l[1] = %d, r[1] = %d\n", l[1], r[1]);
        while(p < m && q[p + 1].r == i) {
            ++p; 
            // debug("res[%d] = query(%d)\n", q[p].id, q[p].l);
            res[q[p].id] = query(q[p].l);
        }
        for(auto &id : resume) reset(id);
    }
    _rep(i,1,m) outln(res[i]);
    return 0;
}