题外话
这道题题面有毒我笑死了 $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]);
}
0 条评论