事情的相似度[loj6041]

发表于 分类于

题目链接

链接

题意

多次询问前缀在 $[l,r]$ 中选两个的最长公共后缀。

$n\leq 10^5$

题解

首先你显然先建一个SAM，然后构造出 fail 树。

接着我想了一个 $n\sqrt n\log n$ 的做法，也就是用莫队，然后每次增加或删除一个点用个 set 去维护它，这个过程需要求个 lca。

不过不需要这么麻烦（也不知能不能过）。

显然将所有的询问离线，按 $r$ 从小到大排序。

对于两个前缀 $a,b$ 的贡献，不妨在 $a$ 那里统计它，那么假设考虑到右端点到 $r$ 时，$a$ 的最大值为 $mx_a$，那么答案就是 $\max_{l\leq i \leq r}{mx_i}$。

现在只需要看这个 $mx_i$ 怎么求。

考虑新加一个节点 $pos_i$ 上去，然后将它到根中所有的点都染成颜色 $i$。那么这条路径中的点之前的颜色就能有贡献，对于一种颜色 $j$，显然染成 $j$ 的节点形成了一条到根的连续的路径。那么颜色 $j$ 的需要跟 $mx_j$ 比较的数就是 $pos_i$ 往根跳的路径中，第一个为颜色 $j$ 的节点的 $len$。

但是你会发现，有些颜色会被覆盖掉，$mx$ 的值不对。不过这是没有关系的，因为是按顺序加进去的，其他颜色会统计这个贡献。

那么就能用上面这种方法了，维护一个不换根的lct，加一个树状数组求单点修改后缀最值即可。

时间复杂度 $O(n\log n)$ 左右？

程序

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
149
150
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
    int x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=2e5+5;
int n,m;
namespace BIT{
    int mx[N];
    inline void add(int x,int d)
    {
        if(!x) return;
        for(;x;x-=lowbit(x)) mx[x]=max(mx[x],d);
    }
    inline int ask(int x)
    {
        int ans=0;
        for(;x<=n;x+=lowbit(x)) ans=max(ans,mx[x]);
        return ans;
    }
}
namespace LCT{
    int fa[N],ch[N][2],col[N],len[N];
    inline bool isroot(int x) {return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
    inline bool son(int x) {return ch[fa[x]][1]==x;}
    inline void rotate(int x)
    {
        int y=fa[x],z=fa[y],d=son(x);
        if(!isroot(y)) ch[z][son(y)]=x; fa[x]=z;
        ch[y][d]=ch[x][1-d]; fa[ch[y][d]]=y;
        ch[x][1-d]=y; fa[y]=x;
    }
    inline void pushdown(int x)
    {
        if(ch[x][0]) col[ch[x][0]]=col[x];
        if(ch[x][1]) col[ch[x][1]]=col[x];
    }
    inline void push(int x) {if(!isroot(x)) push(fa[x]); pushdown(x);}
    inline void splay(int x)
    {
        push(x);
        for(int y=fa[x];!isroot(x);rotate(x),y=fa[x])
            if(!isroot(y)) rotate((son(x)^son(y))?x:y);
    }
    inline void access(int x)
    {
        for(int y=0;x;y=x,x=fa[x])
            splay(x),ch[x][1]=y;
    }
    inline void link(int x,int y)
    {
        if(!x) return;
        access(x); splay(y); splay(x);
        fa[y]=x;
    }
    inline void add(int x,int c)
    {
        for(int y=0;x;y=x,x=fa[x])
            splay(x),BIT::add(col[x],len[x]),col[x]=c,ch[x][1]=y;
    }
}

namespace SAM{
    int ne[N][2],fa[N],len[N],siz,las;
    void init()
    {
        siz=las=1;
    }
    inline int extend(int c)
    {
        int cur=++siz,p=las;
        len[cur]=len[p]+1;
        for(;p&&!ne[p][c];p=fa[p]) ne[p][c]=cur;
        if(!p) fa[cur]=1;
        else
        {
            int q=ne[p][c];
            if(len[q]==len[p]+1) fa[cur]=q;
            else
            {
                int clone=++siz;
                memcpy(ne[clone],ne[q],sizeof(ne[q]));
                len[clone]=len[p]+1; fa[clone]=fa[q];
                for(;p&&ne[p][c]==q;p=fa[p]) ne[p][c]=clone;
                fa[q]=fa[cur]=clone;
            }
        }
        las=cur;
        return cur;
    }
    inline void build()
    {
        fo(i,2,siz) LCT::link(fa[i],i);
        fo(i,1,siz) LCT::len[i]=len[i];
    }
}

struct query{
    int l,r,id;
    friend inline bool operator <(const query &A,const query &B)
    {
        return A.r<B.r;
    }
}q[N];
int pos[N],ans[N];
char s[N];
int main()
{
    n=read(); m=read();
    scanf("%s",s+1);
    SAM::init();
    fo(i,1,n) pos[i]=SAM::extend(s[i]^48);
    SAM::build();
    fo(i,1,m) q[i].l=read(),q[i].r=read(),q[i].id=i;
    sort(q+1,q+m+1);
    for(int i=1,j=1;i<=n;i++)
    {
        LCT::add(pos[i],i);
        for(;j<=m&&q[j].r==i;j++) ans[q[j].id]=BIT::ask(q[j].l);
    }
    fo(i,1,m) printf("%d\n",ans[i]);
    return 0;
}