Wuyanru's blog
0%

[NOI2018] 你的名字

发表于 分类于 ，

苍天啊，大地啊，模拟赛里怎么全是毒瘤题啊！

题目链接：luoguP4770。

这道题让我们求的是 所有本质不同子串中不为 的子串的个数。

首先我们可以利用 SAM 非常简单的求出 的本质不同子串个数。

什么？你不知道怎么求，建议先做luoguP3804 【模板】后缀自动机 (SAM)

下面我们只需要对每一个询问求出包含在 中的 的所有本质不同子串个数就可以了。

68 分做法

我们可以看到，整道题前面 分都有 ，我们不妨先来思考这些测试点怎么做。

如果我们想要知道 的哪些子串同时也是 的子串，最好的方法肯定就是对 建立一个 SAM，然后用 在上面匹配。

因为 SAM 的 fail 的含义与 AC 自动机的差不多，指向的都是该节点代表字符串的后缀。

并且 SAM 中包含一个字符串的所有子串，就相当于是把一个字符串的所有子串抽出来建了一个 AC 自动机。

所以实际上是可以进行匹配的（可能还挺常用？）。

这样子我们就可以知道对于 的每一个前缀 ，它的最长后缀的长度使得这个后缀是 的子串。

但是这样找出的子串并不能保证本质不同。

那么我们把这个过程搬到 SAM 上面。

我们再对 建一个 SAM，并且对于每一个点 再新维护一个信息 ，表示第 个点表示的所有字符串中，长度小于等于 的都是 的子串。

我们只需要把 在 的 SAM 上面跑一遍，然后顺着 parent 边更新答案就可以了（拓扑排序或者 dfs 都行）。

其实上面找 的过程事实上就是这道题，可以做一下加深理解。

然后我们就可以拿到 分了！

满分做法

我们发现，上面的做法不能AC主要原因在于每一次询问的是 的一个子串，我们使用 进行匹配的时候很有可能“越界”，而我们又不能快速得到 的某个子串的 SAM。

我们无法快速得到一个子串的 SAM，那我们能否快速查询某一个节点代表的某个子串是否在 范围内呢？

我们知道，SAM 上某一个节点代表字符串的位置实际上是和它的 endpos 有关的，那么我们能不能快速得到某个节点的 endpos 集合呢？

答案是可以的，我们需要在 SAM 的 parent 上面跑线段树合并。

所以我们只需要在沿边转移的时候加上一个 endpos 的条件即可。

停停，线段树合并不是离线的吗？

所以我们需要进行可持久化线段树合并。

和普通线段树合并不同的一点是，我们每次合并两个节点时新建一个节点，这样就不会破坏原来的节点，并且在所有查询之前进行合并，这样时间复杂度不会变，算法也变成了在线。

然后快乐提交，拿到 分，挂了一个点。

代码

提交记录

哪里挂了呢？

你会发现假如某一个节点因为 endpos 而不能转移时，你直接跳了 fail，但是有可能在匹配长度减小一些以后它又可以转移了。

稍微转移一下就可以过。

代码：

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
template<typename A>
using vc=vector<A>;
using pi=pair<int,int>;
using ll=long long;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int root[1000001];
vc<int>g[1000001];
int ls[30000001];
int rs[30000001];
int son[2000001][26];
int fail[2000001];
int len[2000001];
vc<int>t[100001];
vc<int>w[100001];
char in[1000002];
int mo[2000001];
int ma[2000001];
char s[500002];
ll ans[100001];
int l[100001];
int r[100001];
int cnt=1;
int lst=1;
int tot;
int n,m;
void clear()
{
    for(int i=1;i<=cnt;i++)
    {
        fail[i]=len[i]=ma[i]=0;
        for(int j=0;j<26;j++) son[i][j]=0;
    }
    cnt=lst=1;
}
void add(int a)
{
    int cur=++cnt,p=lst;lst=cur,len[cur]=len[p]+1;
    for(;p&&!son[p][a];p=fail[p]) son[p][a]=cur;
    if(!p){ fail[cur]=1;return ;}
    int q=son[p][a];
    if(len[q]==len[p]+1){ fail[cur]=q;return ;}
    int nq=++cnt;len[nq]=len[p]+1;
    fail[nq]=fail[q],fail[q]=fail[cur]=nq;
    for(int i=0;i<26;i++) son[nq][i]=son[q][i];
    for(;p&&son[p][a]==q;p=fail[p]) son[p][a]=nq;
}
void debug()
{
    // for(int i=1;i<=cnt;i++)
    // {
    //     printf("%d : len=%d fail=%d ",i,len[i],fail[i]);
    //     for(int j=0;j<26;j++) if(son[i][j]) printf("(%c,%d) ",j+'a',son[i][j]);
    //     printf("\n");
    // }
}
void add(int &p,int pl,int pr,int x)
{
    if(!p) p=++tot;
    if(pl==pr) return ;
    int mid=(pl+pr)>>1;
    if(x<=mid) add(ls[p],pl,mid,x);
    else add(rs[p],mid+1,pr,x);
}
int merge(int u,int v,int pl,int pr)
{
    if(!u||!v) return u|v;
    int ans=++tot;
    if(pl==pr) return ans;
    int mid=(pl+pr)>>1;
    ls[ans]=merge(ls[u],ls[v],pl,mid);
    rs[ans]=merge(rs[u],rs[v],mid+1,pr);
    return ans;
}
void dfs(int num)
{
    for(int p:g[num]) dfs(p),root[num]=merge(root[num],root[p],1,m);
}
void topo()
{
    queue<int>que;
    for(int i=2;i<=cnt;i++) mo[fail[i]]++;
    for(int i=1;i<=cnt;i++) if(!mo[i]) que.push(i);
    while(!que.empty())
    {
        int p=que.front();que.pop();
        ma[fail[p]]=max(ma[fail[p]],ma[p]),mo[fail[p]]--;
        if(!mo[fail[p]]) que.push(fail[p]);
    }
}
bool get(int p,int pl,int pr,int l,int r)
{
    // printf("get %d %d %d %d %d\n",p,pl,pr,l,r);
    if(!p) return false;
    if(l<=pl&&pr<=r) return true;
    int mid=(pl+pr)>>1;
    if(l<=mid&&get(ls[p],pl,mid,l,r)) return true;
    if(mid<r&&get(rs[p],mid+1,pr,l,r)) return true;
    return false;
}
int main()
{
    // freopen("name.in","r",stdin);
    // freopen("name.out","w",stdout);
    scanf("%s",s+1),n=read(),m=strlen(s+1);
    for(int i=1;s[i];i++) add(s[i]-'a');
    for(int i=1,now=1;s[i];i++) now=son[now][s[i]-'a'],add(root[now],1,m,i);
    for(int i=2;i<=cnt;i++) g[fail[i]].push_back(i);
    dfs(1),debug();
    // for(int i=1;i<=cnt;i++) printf("%d ",root[i]);
    // printf("\n");
    for(int i=1;i<=n;i++)
    {
        scanf("%s",in+1);int l=read(),r=read(),now=1,le=0;
        for(int j=1;in[j];j++)
        {
            t[i].push_back(in[j]-'a');
            while(true)
            {
                if(son[now][in[j]-'a']&&le<=r-l&&get(root[son[now][in[j]-'a']],1,m,l+le,r))
                {
                    now=son[now][in[j]-'a'],le++;
                    break;
                }
                if(!le) break;
                // printf("le : %d -> %d\n",le,le-1);
                le--;
                if(len[fail[now]]==le) now=fail[now];
            }
            w[i].push_back(le);
            // printf("j=%d : now=%d le=%d\n",j,now,le);
            // printf("%d ",le);
        }
        // printf("\n");
    }
    for(int i=1;i<=n;i++)
    {
        clear();
        for(unsigned j=0;j<t[i].size();j++) add(t[i][j]);
        for(int j=0,now=1;j<(int)t[i].size();j++)
        {
            now=son[now][t[i][j]];
            ma[now]=max(ma[now],w[i][j]);
            // printf("%d : %d\n",now,w[i][j]);
        }
        topo();
        for(int j=2;j<=cnt;j++)
        {
            ans[i]-=max(0,min(len[j],ma[j])-len[fail[j]]);
            ans[i]+=len[j]-len[fail[j]];
        }
    }
    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
    return 0;
}