Reincarnation

正因为梦易碎，才格外美好。

DAG 链剖分 & 基本子串字典

发表于 更新于 分类于 ，
本文字数： 10k 阅读时长 ≈ 9 分钟

“吾身殉道，吾心独行。”

更新日志

：起稿。

DAG 剖分

考虑一种很新的 做法，这个算法由广为人知的 学长在 年的论文中被提及到，但很显然，一个算法在被提及之前就会很早在国际上昙花一现，据说第一次出现是在 上，这个我们之后再谈。

算法 & 实现

与树链剖分类似，通过设置一个与其它结点不同的特殊结点把整张图划分成若干条链，使链上操作的平摊趋于一个可接受范围内的复杂度分析。在重链剖分中，这个特殊结点是重儿子（子树大小最大的儿子），而在长链剖分中，则是长儿子（子树深度最深的儿子）。

首先， 可能存在若干个入度为 的点，他们之间两两不相干，所以考虑新建源点 ，并把 连向上述所有点，如此，整个 上只会存在一个入度为 的点，我们将其视作 链剖分的「根」。

设 表示从 结点出发的路径个数，并定义其重后继（重儿子）为所有 中 ，也就是 最大的结点；反过来，记录 表示以 为终点的路径个数，定义其重前驱为指向 的结点中 最大的，分别记录为 。

我们将某一些边 称作重边，当且仅当这条边满足 ，如果在原图中把所有非重边全部删除的话，剩余的图就会由若干条不相交的重链组成。

由所有重链组成的这个非完全图构成内向森林（每一个结点出度为 ）。

下面有一个 的例子：

img

其重链图组成如下：

img

我们知道，在树链剖分中，保证重链的个数和长度都是 级，以保证其区间维护时间复杂度在 级。那么，我们也将来探讨有关 链剖分的时间复杂度保证证明。

对于结点 ，令其重后继为 ，其另一个轻后继为 ，则一定存在 ，这意味着 ，也就是 ，而很显然的， 一定不属于同一条重链，那么每跳一次链（从一条链到另一条链），其 值就会至少减少为 ，同理，可以证明出，每条一次链， 值会至少增加为 倍。

所以，根据上面所说的，任意一条路径上的重链个数（轻边个数）都是 级的。其中 是路径条数。

相似地， 链剖分同样存在全局平衡二叉树优化，但这确实看起来十分阴间的，所以笔者不会过多提及。

运用

读者认为这么个高级图论的东西出了快一年多了，怎么感觉从来没遇到呢。那当然，就 放在论文里的那几道例题以及扩展根本就不是常人能够触及的，那现在我们来看看 链剖分较为常规的运用，与另外一个阴间玩意儿——后缀自动机的结合。

从 的学习中我们可知，一个字符串 所构造出的 的 （，有向无环词图）路径数是 的本质不同子串数，而且在 中可以做到用 条时间戳维护从 到 的路径。

例题

Border 的第五种求法

题目简介

题目名称： 的第五种求法

题目来源：

评测链接：https://uoj.ac/problem/752

形式化题意：给定一个由小写字母组成的长度为 的字符串 ，以及一个长度为 的函数 ，定义一个字符串 的权值为这个字符串在 中出现的次数 代表的 。共 次询问，求 的所有 的价值和。

数据范围：

时空限制：

首先得找到 的所有 ，然后得统计所有 在 的出现个数，然后转化成 求和，所以一共是 步。考虑怎么解决。

首先对 建出 ，那么对于一个子串 ，如果 是 的 ，则 应该满足以下条件：

  • 是 的前缀；
  • 在 树上是 的祖先。

我们考虑 的贡献形式，这个子串一定是 中的一条路径，那我们考虑对 进行 链剖分，把整个路径拆分成 条时间戳连续的重链。路径上结点与其后缀树链上的结点的交集就是这个子串的 ，我们可以直接通过计算 来得到答案。

我们首先 维护树链上的点在 链上的分布情况，然后通过 维护求和，在树上二分求字符串哈希求 ，最后转化成二维数点，用 维护即可。

AC 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
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
// ----- Eternally question-----
// Problem: #752. 【UNR #6】Border 的第五种求法
// Contest: UOJ
// URL: https://uoj.ac/problem/752
// Memory Limit: 1200 MB
// Time Limit: 6000 ms
// Written by: Eternity
// Time: 2023-07-23 16:19:40
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
const int MAXN=1e6+10,MAXK=20,MAXS=27;
namespace SA
{
	int Cnt[MAXN],Rk[MAXN],Sa[MAXN];
	int Id[MAXN],Lstrk[MAXN],Key[MAXN];
	int Len,M;
	int Lg[MAXN],Mul[MAXK][MAXN];
	inline bool cmp(int i,int j,int w)
	{ return Lstrk[i]==Lstrk[j]&&Lstrk[i+w]==Lstrk[j+w]; }
	inline void build(char *s)
	{
		Len=std::strlen(s+1),M=1<<7;
		for(int i=1;i<=Len;++i) ++Cnt[Rk[i]=s[i]];
		for(int i=1;i<=M;++i) Cnt[i]+=Cnt[i-1];
		for(int i=Len;i>=1;--i) Sa[Cnt[Rk[i]]--]=i;
		for(int w=1,p,i;;w<<=1,M=p)
		{
			for(p=0,i=Len;i>Len-w;--i) Id[++p]=i;
			for(i=1;i<=Len;++i) if(Sa[i]>w) Id[++p]=Sa[i]-w;
			std::memset(Cnt,0,sizeof(Cnt));
			for(i=1;i<=Len;++i) ++Cnt[Key[i]=Rk[Id[i]]];
			for(i=1;i<=M;++i) Cnt[i]+=Cnt[i-1];
			for(i=Len;i>=1;--i) Sa[Cnt[Key[i]]--]=Id[i];
			std::memcpy(Lstrk+1,Rk+1,Len*sizeof(int));
			for(p=0,i=1;i<=Len;++i) Rk[Sa[i]]=cmp(Sa[i],Sa[i-1],w)?p:++p;
			if(p==Len) break;
		}
		for(int i=2;i<=Len;++i) Lg[i]=Lg[i>>1]+1;
		for(int i=1,k=0;i<=Len;++i)
		{
			if(k) --k;
			while(s[i+k]==s[Sa[Rk[i]-1]+k]) ++k;
			Mul[0][Rk[i]]=k;
		}
		for(int s=1;s<=Lg[Len];++s)
			for(int i=1;i+(1<<s)-1<=Len;++i)
				Mul[s][i]=std::min(Mul[s-1][i],Mul[s-1][i+(1<<(s-1))]);
	}
	inline int getLcp(int x,int y)
	{
		if(x==y) return Len-x+1;
		if((x=Rk[x])>(y=Rk[y])) std::swap(x,y);
		int lg=Lg[y-x++];
		return std::min(Mul[lg][x],Mul[lg][y-(1<<lg)+1]);
	}
	inline int lcp(int a,int b,int c,int d){ return std::min(std::min(b-a,d-c)+1,getLcp(a,c)); }
};
namespace SAM
{
	int Idx=1,last=1,s[MAXN];
	int len[MAXN],nxt[MAXN][MAXS],fa[MAXN];
	int siz[MAXN],lst[MAXN],pos[MAXN];
	inline void insert(int c)
	{
		int cur=++Idx,p=last;
		last=cur;
		len[cur]=len[p]+1;pos[len[cur]]=cur;
		siz[cur]=1,s[len[cur]]=c;
		while(!nxt[p][c]) nxt[p][c]=cur,p=fa[p];
		if(!p) return fa[cur]=1,void();
		int q=nxt[p][c];
		if(len[p]+1==len[q]) return fa[cur]=q,void();
		int cl=++Idx;
		std::memcpy(nxt[cl],nxt[q],MAXS<<2);
		fa[cl]=fa[q],fa[q]=fa[cur]=cl;
		len[cl]=len[p]+1;
		while(nxt[p][c]==q) nxt[p][c]=cl,p=fa[p];
	}
	bool Vis[MAXN];
	ll f[MAXN],g[MAXN];
	std::vector<int>Edges[MAXN],G[MAXN],R[MAXN];
	inline void calc(int x)
	{
		lst[x]=len[x];
		for(int v:Edges[x]) calc(v),siz[x]+=siz[v],lst[x]=lst[v];
	}
	ll calcf(int x)
	{
		if(Vis[x]) return f[x];
		Vis[x]=1,f[x]=1;
		for(int v:G[x]) f[x]+=calcf(v);
		return f[x];
	}
	ll calcg(int x)
	{
		if(Vis[x]) return g[x];
		Vis[x]=1,g[x]=1;
		for(int v:R[x]) g[x]+=calcg(v);
		return g[x];
	}
	int To[MAXN],tag[MAXN];
	int Cnt,Dfn[MAXN],Rev[MAXN],Top[MAXN];
	int End[MAXN],_l[MAXN],_r[MAXN];
	void dfs(int x,int topf)
	{
		Rev[Dfn[x]=++Cnt]=x;
		Top[x]=topf,End[x]=x;
		if(To[x]) dfs(To[x],topf),End[x]=End[To[x]];
		if(x==topf) _r[x]=lst[End[x]],_l[x]=_r[x]-(Dfn[End[x]]-Dfn[x])+1;
		for(int v:G[x]) if(!Dfn[v]&&!tag[v]) dfs(v,v);
	}
	inline void build()
	{
		for(int i=2;i<=Idx;++i) Edges[fa[i]].push_back(i);
		calc(1);
		for(int i=1;i<=Idx;++i)
			for(int c=0;c<26;++c)
				if(nxt[i][c])
				{
					G[i].push_back(nxt[i][c]);
					R[nxt[i][c]].push_back(i);
				}
		for(int i=1;i<=Idx;++i) calcf(i);
		std::memset(Vis,0,sizeof(Vis));
		for(int i=1;i<=Idx;++i) calcg(i);
		for(int i=1;i<=Idx;++i)
			for(int v:G[i]) if(2*f[v]>f[i]&&2*g[i]>g[v]) To[i]=v,tag[v]=1;
		dfs(1,1);
	}
	inline std::vector<Pir> get(int x,int y)
	{
		int p=1;
		std::vector<Pir>ret;
		while(true)
		{
			int l=_l[Top[p]],r=_r[Top[p]];
			l+=Dfn[p]-Dfn[Top[p]];
			if(l<=r)
			{
				int mat=SA::lcp(l,r,x,y);
				ret.push_back({Dfn[p],Dfn[p]+mat});
				x+=mat,p=Rev[Dfn[p]+mat];
			}
			else ret.push_back({Dfn[p],Dfn[p]});
			if(x<=y)
			{
				if(To[p]==nxt[p][s[x]]) exit(0);
				p=nxt[p][s[x++]];
			}
			else break;
		}
		return ret;
	}
};
int N,Q,f[MAXN];
char Str[MAXN];
std::vector<Pir>Seq[MAXN];
std::vector<int>Buc[MAXN];
ll ans[MAXN];
struct BIT
{
	ll Tre[MAXN];
	inline int lowbit(int x){ return x&(-x); }
	inline void add(int x,int v){ for(;x<=SAM::Idx;x+=lowbit(x)) Tre[x]+=v; }
	inline ll query(int x)
	{
		ll res=0;
		for(;x;x-=lowbit(x)) res+=Tre[x];
		return res;
	}
	inline ll get(int l,int r){ return query(r)-query(l-1); }
}Tre;
void solve(int x)
{
	if(x>1) Tre.add(SAM::Dfn[x],f[SAM::siz[x]]);
	for(int v:Buc[x]) for(auto it:Seq[v]) ans[v]+=Tre.get(it.fir,it.sec);
	for(int v:SAM::Edges[x]) solve(v);
	if(x>1) Tre.add(SAM::Dfn[x],-f[SAM::siz[x]]);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q),scanf("%s",Str+1);
	for(int i=1;i<=N;++i) read(f[i]);
	for(int i=1;i<=N;++i) SAM::insert(Str[i]-'a');
	SA::build(Str),SAM::build();
	for(int i=1,ql,qr;i<=Q;++i)
	{
		read(ql,qr);
		Buc[SAM::pos[qr]].push_back(i);
		Seq[i]=SAM::get(ql,qr);
	}
	solve(1);
	for(int i=1;i<=Q;++i) write(ans[i],'\n');
	return 0;
}
/*

*/

Ж-function

题目简介

题目名称：Ж

题目来源：

评测链接：https://codeforces.com/problemset/problem/1098/F

形式化题意：给定一个字符串 ，定义函数 表示 的所有后缀与 本身的 之和。共 次询问，求 。

数据范围：

基本字串字典

这个黑科技被发明出来大概是为了解决一些令人头疼的有关 的问题，这个我们也都或多或少见识过一些，大多数情况下都是需要构建 后树剖维护，当然，也存在一些复杂度不够优美但是易写的方式，笔者想，大概有时间会专门写一篇学习笔记针对 相关的问题。这里不做过多赘述。

定义

我们考虑一种很新的方式来解决字符串问题，现在想象一个二维平面 ，我们在点对 处放上 的子串 ，那么一共会有 个点有子串。

现在定义两个面向字符串的函数 和 ，其中 在 中出现的次数，而 表示最长的 使得 ，也就是最长的子串使得这个子串和 在 中的出现次数相同。

而对于一些子串，他们的 相同，我们将其称为一个 等价类。我们再记满足 的字符串为这个 等价类的 ，称作代表元。而 表示的就是 等价类。

类似于研究 的基本结构，我们也来研究一下 的性质。

ext的性质

引理

存在且唯一，对于 ，如果存在 ，那么一定有 。且 。

引理

存在且唯一。若 且 ，那么 。

相关文章