传送门

题外话

这道题题面有毒我笑死了 $qwq$

不过题面第一句话读了有点伤感 $QAQ$

题解

这是一道加深对后缀自动机理解的好题呀 $qwq$

首先简化一下题意,我们就是要找一对 $(x,y)\in [l,r]\;x\ne y$,使得字符串 $S_{1,l}$和 $S_{1,r}$的最长公共后缀最长

显然这两个字符串在后缀自动机上是有一个点代表的的,我们记为 $u,v$,然后它们两个的最长公共后缀的长度就是 $u$和 $v$的在 $par$树上的 $lca$的 $len$值。

所以我们将问题转化为,令 $a[l]$表示 $trans(S_{1,l})$(也就是这个字符串所代表在后缀自动机上的点),那么每次询问相当于就是求 $max\{len[lca(x,y)]\}$,其中 $x,y$就是上面提到的那对数,但是显然我们这样枚举 $(x,y)$复杂度首先会 $gg$,于是我们考虑怎样进一步优化

注意到一个被包含的数对 $(x,y)$是可以对包含它的区间 $(l,r)\; x\leq l,r\leq y\;$作贡献的

我们可以枚举一个 $lca$,枚举它的儿子,将儿子里有的数合并,并且找出能对答案贡献 $len[lca]$的数对,用一个结构体记录 $(x,y,val)$表示数对和贡献的值,然后将询问离线,就是一个典型的二维数点问题了,直接排序+树状数组维护就好了

感觉自己还是说的好糊,看看代码的 $merge()$函数,自己画画 $par$树大概也能理解吧

#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mod 1000000007
#define eps 1e-4
#define lowbit(x) (x & -x)
#define N 100005
int n, m;
int ch[N << 1][2], pre[N << 1], step[N << 1], x, cnt = 1, last = 1, sz[N << 1];
inline void ins (int x)
{
    int p = last, np = ++cnt;
    last = cnt; step[np] = step[p] + 1; sz[np] = 1;
    while (p && !ch[p][x])
        ch[p][x] = np, p = pre[p];
    if (!p)
        pre[np] = 1;
    else
    {
        int q = ch[p][x];
        if (step[q] == step[p] + 1)
            pre[np] = q;
        else
        {
            int nq = ++cnt;
            step[nq] = step[p] + 1;
            fo (i, 0, 1) ch[nq][i] = ch[q][i];
            pre[nq] = pre[q]; pre[q] = pre[np] = nq;
            while (ch[p][x] == q) ch[p][x] = nq, p = pre[p];
        }
    }
}
char c;
struct node {
    int x, y, v;
    friend bool operator < (node x, node y)
    {
        return x.x > y.x;
    }
} t[N * 40], q[N];
std::set<int> s[N << 1];
int a[N << 1], b[N << 1], tot;
#define itset std::set<int>::iterator
inline void merge ()
{
    fo (i, 1, cnt) ++a[step[i]];
    fo (i, 1, n) a[i] += a[i - 1];
    fo (i, 1, cnt) b[a[step[i]]--] = i;
    fd (i, cnt, 2)
    {
        int u = b[i], p = pre[u];
        if (s[u].size() > s[p].size()) std::swap(s[u], s[p]);
        for (itset it = s[u].begin(); it != s[u].end(); ++it)
        {
            itset pos = s[p].lower_bound(*it);
            if (pos != s[p].end()) t[++tot] = (node) {*it, *pos, step[p]};
            if (pos != s[p].begin()) t[++tot] = (node) {*(--pos), *it, step[p]};
        }
        for (itset it = s[u].begin(); it != s[u].end(); ++it) s[p].insert(*it);
    }
}
int ans[N], T[N];
inline void update (int u, int val) { for (int i = u; i <= n; i += lowbit(i)) T[i] = std::max(T[i], val); }
inline int query (int u) { int ret = 0; for (int i = u; i; i -= lowbit(i)) ret = std::max(T[i], ret); return ret; }
int main ()
{
    scanf("%d %d", &n, &m);
    fo (i, 1, n)
    {
        c = getchar();
        while (!isdigit(c)) c = getchar();
        s[cnt + 1].insert(i);
        ins(c == '1');
    }
    merge();
    fo (i, 1, m)
    {
        scanf("%d %d", &q[i].x, &q[i].y);
        q[i].v = i;
    }
    std::sort(q + 1, q + m + 1); std::sort(t + 1, t + tot + 1);
    int j = 1;
    fo (i, 1, m)
    {
        while (j <= tot && q[i].x <= t[j].x) update(t[j].y, t[j].v), ++j;
        ans[q[i].v] = query(q[i].y);
    }
    fo (i, 1, m) printf("%d\n", ans[i]);
}
分类: 文章

quhengyi11

AFO 有缘再见

发表评论

电子邮件地址不会被公开。 必填项已用*标注