「LOJ 6041」「雅礼集训 2017 Day7」事情的相似度

发表于

人的一生不仅要靠自我奋斗，还要考虑到历史的行程。

历史的行程可以抽象成一个 0101 串，作为一个年纪比较大的人，你希望从历史的行程中获得一些姿势。

你发现在历史的不同时刻，不断的有相同的事情发生。比如，有两个人同时在世纪之交 1111 年的时候上台，同样喜欢与洋人谈笑风生，同样提出了以「三」字开头的理论。

你发现，一件事情可以看成是这个 0101 串的一个前缀，这个前缀最右边的位置就是这个事情的结束时间。

两件事情的相似度可以看成，这两个前缀的最长公共后缀长度。

现在你很好奇，在一段区间内结束的事情中最相似的两件事情的相似度是多少呢？

Constraints

1≤n,m≤1051 \leq n,m \leq 10^5

Solution

建出原串的 SAM ，则两个前缀的最长公共后缀为他们在 parent 树上的 lca ，问题转化为求区间内前缀两两 lca 深度的最大值。

将询问离线，按右端点从小到大排序。我们考虑每次加入一个字母，就将他们在 parent 树上到根节点的路径打上他们的标记。往根节点跑的过程中，若遇到了以前打的标记，则该节点为旧标记与新标记的 lca 。贪心可得应把标记尽量覆盖为较大的值。用树状数组来统计答案，下标为左端点，每次查询下标大于等于该询问左端点的最大深度。向根跑的过程中每一次遇到旧标记，就在树状数组上更新答案，并给该节点打上新标记。

往根节点跑的过程实际上就是 LCT 的 access 。

Code

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
#include<cstdio>
#include<algorithm> 
#include<cstring>
#include<vector>
#define LL long long
using namespace std;
const int N=1e5+5;
int n,m,r,last,size,root;
int p[N],mx[N],ans[N],num[N];
int c[N*2][2],fa[N*2],v[N*2],tag[N*2];
char s[N];
vector<int> q[N];
struct sam{int mx,fa,ch[2];}t[N*2];
int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int lowbit(int x){return x&(-x);}
void modify(int x,int v){x=n-x+1;while(x<=n)mx[x]=max(mx[x],v),x+=lowbit(x);}
int query(int x){x=n-x+1;int ans=0;while(x)ans=max(ans,mx[x]),x-=lowbit(x);return ans;}
void ins(int c,int id)
{
    int np=++size;num[id]=np;
    t[np].mx=t[last].mx+1;
    int x=last;last=np;
    while(x&&!t[x].ch[c])t[x].ch[c]=np,x=t[x].fa;
    if(!x)t[np].fa=root;
    else
    {
        int y=t[x].ch[c];
        if(t[y].mx==t[x].mx+1)t[np].fa=y;
        else
        {
            int nq=++size;
            t[nq]=t[y];t[nq].mx=t[x].mx+1;
            t[y].fa=t[np].fa=nq;
            while(x&&t[x].ch[c]==y)t[x].ch[c]=nq,x=t[x].fa;
        }
    }
}
bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
void change(int x,int val){v[x]=tag[x]=val;}
void down(int x)
{
    if(!tag[x])return;
    if(c[x][0])change(c[x][0],tag[x]);
    if(c[x][1])change(c[x][1],tag[x]);
    tag[x]=0;
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],l,r;
    if(c[y][0]==x)l=0;else l=1;r=l^1;
    if(!isroot(y)){if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;}
    fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
    c[y][l]=c[x][r];c[x][r]=y;
}
void relax(int x){if(!isroot(x))relax(fa[x]);down(x);}
void splay(int x)
{
    relax(x);
    while(!isroot(x))
    {
        int y=fa[x],z=fa[y];
        if(!isroot(y))
        {
            if((c[y][0]==x)^(c[z][0]==y))rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}
void access(int x,int val)
{
    int o=0;
    while(x)
    {
        splay(x);modify(v[x],t[x].mx);
        c[x][1]=o;o=x;x=fa[x];
    }
    tag[o]=v[o]=val;
}
void build(){for(int i=1;i<=size;i++)fa[i]=t[i].fa;}
int main()
{
    n=read();m=read();
    scanf("%s",s+1);
    for(int i=1;i<=m;i++)
    {
        p[i]=read();r=read();
        q[r].push_back(i);
    }
    last=size=root=1;
    for(int i=1;i<=n;i++)ins(s[i]-'0',i);
    build();
    for(int i=1;i<=n;i++)
    {
        access(num[i],i);
        int sz=q[i].size();
        for(int j=0;j<sz;j++)
        {
            int x=q[i][j];
            ans[x]=query(p[x]);
        }
    }
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}