题解
(SAM+set)启发式合并+扫描线
首先可以发现题目要求的就是查询结尾在一段区间内的(LCS)
这个显然就是(SAM)的(parent)树上的(step[LCA])
我们可以对后缀自动机的每个节点(u)开一个(set)来维护(endpos)集合
然后对(u)的儿子的(right)集合启发式合并,(u)的儿子和(u)当前集合内的点的(LCS)就是(step[u])
显然在贡献是相同的情况下距离越近的越有效
所以我们对于要合并的点的一个位置(u)只需要找这个位置的前驱和后继并加入点对即可
这样我们处理出了若干个((x,y,v))的点对
那么对于一个询问(l,r)
有贡献的点对就是(lle x , r > y)
所以我们就把所有的点对和询问按照右端点排序
每扫到一个点对((x,y,v))
就把(x)位置加上(v)
查询就是查(l)位置之前的最大值
代码
#include<set>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 400005 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
char s[M] ;
int n , m , tot ;
int Last , cnt ;
int fa[M] , st[M] , son[M][2] ;
int b[M] , c[M] , ans[M] ;
multiset < int > S[M] ;
struct Q {
int l , r , idx ;
} q[M] ;
struct Node {
int x , y , v ;
Node () { } ;
Node (int Tx , int Ty , int Tv) {
x = Tx , y = Ty , v = Tv ;
if(x > y) swap(x , y) ;
}
} pi[M * 10] ;
inline bool operator < (Q A , Q B) {
return A.r < B.r ;
}
inline bool operator < (Node A , Node B) {
return A.y < B.y ;
}
inline void Insert(int c) {
int np = ++ cnt , p = Last ; Last = np ; st[np] = st[p] + 1 ;
while(p && !son[p][c]) son[p][c] = np , p = fa[p] ;
if(!p) fa[np] = 1 ;
else {
int q = son[p][c] ;
if(st[q] == st[p] + 1) fa[np] = q ;
else {
int nq = ++ cnt ; st[nq] = st[p] + 1 ;
memcpy(son[nq] , son[q] , sizeof(son[q])) ;
fa[nq] = fa[q] ; fa[q] = fa[np] = nq ;
while(p && son[p][c] == q) son[p][c] = nq , p = fa[p] ;
}
}
}
struct BIT {
int c[M] ;
inline int lowbit(int k) { return (k & (-k)) ; }
inline void change(int k , int x) { while(k) c[k] = max(c[k] , x) , k -= lowbit(k) ; }
inline int query(int k) { int ret = 0 ; while(k <= n) ret = max( ret , c[k] ) , k += lowbit(k) ; return ret ; }
} T ;
inline void Solve() {
int lst = 1 ;
for(int i = 1 ; i <= m ; i ++) {
for(int j = lst ; j <= tot ; j ++) {
if(q[i].r >= pi[j].y) {
T.change(pi[j].x , pi[j].v) ;
lst = j + 1 ;
}
else break ;
}
ans[q[i].idx] = T.query(q[i].l) ;
}
}
int main() {
n = read() ; m = read() ;
scanf("%s",s + 1) ; Last = cnt = 1 ;
for(int i = 1 ; i <= n ; i ++) {
Insert(s[i] - '0') ;
S[Last].insert(i) ;
}
for(int i = 1 ; i <= cnt ; i ++) ++ c[st[i]] ;
for(int i = 1 ; i <= n ; i ++) c[i] += c[i - 1] ;
for(int i = cnt ; i >= 1 ; i --) b[c[st[i]] --] = i ;
for(int i = cnt , p ; i >= 1 ; i --) {
p = b[i] ;
if(!fa[p]) continue ;
if(S[fa[p]].size() < S[p].size())
swap(S[fa[p]] , S[p]) ;
set < int >::iterator it , nw , pre , nxt ;
for(it = S[p].begin() ; it != S[p].end() ; ++it) {
S[fa[p]].insert(*it) ;
nw = pre = nxt = S[fa[p]].find(*it) ; ++ nxt ;
if(pre != S[fa[p]].begin()) -- pre , pi[++tot] = Node (*pre , *nw , st[fa[p]]) ;
if(nxt != S[fa[p]].end()) pi[++tot] = Node (*nw , *nxt , st[fa[p]]) ;
S[fa[p]].erase(*it) ;
}
for(it = S[p].begin() ; it != S[p].end() ; ++it)
S[fa[p]].insert(*it) ;
}
for(int i = 1 ; i <= m ; i ++)
q[i].idx = i , q[i].l = read() , q[i].r = read() ;
sort(q + 1 , q + m + 1) ;
sort(pi + 1 , pi + tot + 1) ;
Solve() ;
for(int i = 1 ; i <= m ; i ++)
printf("%d
",ans[i]) ;
return 0 ;
}