「SOL」事情的相似度(LOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

「SOL」事情的相似度(LOJ)

发表于 分类于 Valine：

回头补字符串（从SAM开始）

# 题面

给定一个长度为 $n$ 的 01 字符串 $S$，记以 $i$ 位置结束的前缀为 $S[i]$。

给定 $m$ 组询问，每组询问给出 $l,r$，求

数据规模：$n,m\le 10^5$。

# 解析

考虑建出 SAM，记 SAM 上代表前缀 $i$ 的节点为 $p_i$，则有 $\operatorname{LCS}(S[i],S[j])$ 为 parent 树上 $p_i,p_j$ 的 LCA 代表的最长字符串长度。

由此分析以下两种做法。

- SOLUTION 1. 启发式合并

考虑在 parent 树上由子树向上合并。

用 set 维护出子树 $i$ 中包含了哪些前缀，记这个集合为 $E_i$，合并只需将子节点 $v$ 的 $E_v$ 与父节点 $u$ 的 $E_u$ 合并后的结果赋给新的 $E_u$ 即可。

通过启发式合并，每次暴力将较小的集合中的元素插入较大集合，可以做到 $\mathcal{O}(n\log^2n)$。

再考虑如何计算答案。当子节点 $v$ 的信息合并到父节点 $u$ 上时，考虑每对 $(i,j)$：$i\in E_v$, $j\in E_u$；$p_i,p_j$ 的 LCA 就是点 $u$。

显然每对 $(i,j)$ 的 LCS 可以贡献到满足 $l\le \min\{i,j\}< \max\{i,j\}\le r$ 的询问 $(l,r)$。

那么我们只需要合并时记录下三元组 $(i,j,x)$，表示 $LCS(S[i],S[j])=x$。对询问离线，two-point + 树状数组 即可回答询问。

但是我们发现三元组的数量是 $\mathcal{O}(n^2)$ 的，不能接受。观察之前的过程，发现许多三元组是无用的——

在合并 $E_u,E_v$ 时，对于每个 $i\in E_u$，我们只需要找到 $E_v$ 中 $i$ 的 “前驱” 和 “后继” $j$。因为比前驱更小的 $j$，其能够贡献到的 $(l,r)$ 的范围更小，比后继更大的 $j$ 同理。

合并次数是 $\mathcal{O}(n\log n)$，于是三元组的数量也是 $\mathcal{O}(n\log n)$。

用 two-point + 树状数组，具体地：

  • 将询问 $(l,r)$ 挂在 $r$；
  • 从左到右枚举右端点 $r_0$，枚举三元组 $(l_0,r_0,x_0)$，更新 $l< l_0$ 的询问的答案与 $x_0$ 取 max；
  • 因为取 max 不存在删除操作，也就不必要讨论树状数组无可减性的限制，只需树状数组维护后缀 max 即可回答挂在 $r$ 的询问。

复杂度也是 $\mathcal{O}(n\log^2n)$。

- SOLUTION 2. LCT

同样对询问离线，将 $(l,r)$ 挂在 $r$ 处。

考虑一种求树上 LCA 的方法。求 $u,v$ 的 LCA，可以将根到 $u$ 的路径上打上 $u$ 的标记，然后从 $v$ 向上爬，找到第一个有 $u$ 的标记的点，即为 LCA。

于是我们可以这样解决这个问题：

  • 从左到右加入右端点 $r$；
  • 从 $p_r$ 开始向根爬，对路上找到的每个标记 $l$，同样记录三元组 $(l,r,x)$ 表示 $LCS(S[i],S[j])=x$；
  • 将 $p_r$ 到根的路径打上 $r$ 的标记。

但是显然一个点上会被盖很多标记，这样复杂度就不优了。

实际上我们只需要保留每个点上最大的标记，和 SOLUTION 1 一样的道理，因为与 $p_r$ LCA 相同的 $p_l$ 只有 $l$ 最大的能够贡献到的询问是最多的。

因为我们是从小到大插入 $r$，保留最大的就相当于直接覆盖。

然后考虑如何实现这个过程，不妨观察一下……

这不是 LCT 的 access 操作吗？

所以直接用 LCT，就可以同时找到链上的标记，以及给链打标记了。

# 源代码

- 启发式合并

点击展开/折叠代码 
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
/*Lucky_Glass*/
#include<set>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int rin(int &r){
	int b=1,c=getchar();r=0;
	while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*=b;
}
const int N=1e5+10;
#define con(type) const type &
typedef set<int>::iterator iter;

struct Segment{
	int le,ri,key;
	Segment(){}
	Segment(con(int)_le,con(int)_ri,con(int)_key):le(_le),ri(_ri),key(_key){}
}seg[N*20];
bool cmpSegment(con(Segment)u,con(Segment)v){return u.ri<v.ri;}

int nseg;

struct Node{
	int nxt[2],len,fa;
	inline int& operator [](con(int)i){return nxt[i];}
};
struct SamAuto{
	int bin[N],setid[N<<1],idx[N<<1],ncnt,rt,lasnod;
	Node nod[N<<1];
	set<int> endpos[N<<1];
	int newNode(con(int)_len){
		int p=++ncnt;nod[p].len=_len;
		return p;
	}
	void extend(con(int)c,con(int)id){
		int p=lasnod,np=newNode(nod[p].len+1);
		lasnod=np;
		endpos[np].insert(id);
		while(p && !nod[p][c]) nod[p][c]=np,p=nod[p].fa;
		if(!p) nod[np].fa=rt;
		else{
			int q=nod[p][c];
			if(nod[q].len==nod[p].len+1) nod[np].fa=q;
			else{
				int nq=newNode(0);
				nod[nq]=nod[q],nod[nq].len=nod[p].len+1;
				nod[q].fa=nod[np].fa=nq;
				while(p && nod[p][c]==q) nod[p][c]=nq,p=nod[p].fa;
			}
		}
	}
	void build(char *str,con(int)len){
		rt=lasnod=newNode(0);
		for(int i=1;i<=len;i++) extend(str[i]-'0',i);
	}
	void solve(con(int)len){
		for(int i=1;i<=ncnt;i++) bin[nod[i].len]++,setid[i]=i;
		for(int i=1;i<=len;i++) bin[i]+=bin[i-1];
		for(int i=1;i<=ncnt;i++) idx[bin[nod[i].len]--]=i;
		for(int i=ncnt;i>1;i--){
			int u=idx[i],uid=setid[u],fid=setid[nod[u].fa],key=nod[nod[u].fa].len;
			if(endpos[uid].size()>endpos[fid].size()) swap(uid,fid);
			for(iter it=endpos[uid].begin();it!=endpos[uid].end();it++){
				iter tmp=endpos[fid].lower_bound(*it);
				if(tmp!=endpos[fid].end()) seg[++nseg]=Segment(*it,*tmp,key);
				if(tmp!=endpos[fid].begin()) tmp--,seg[++nseg]=Segment(*tmp,*it,key);
			}
			for(iter it=endpos[uid].begin();it!=endpos[uid].end();it++)
				endpos[fid].insert(*it);
			setid[nod[u].fa]=fid;
		}
	}
}sam;

struct TreeArray{
	#define lowbit(x) ((x)&(-(x)))
	int ary[N],siz;
	void init(con(int)_siz){siz=_siz;}
	void modify(con(int)pos,con(int)key){
		for(int i=pos;i<=siz;i+=lowbit(i))
			ary[i]=max(ary[i],key);
	}
	int query(con(int)pos){
		int ret=0;
		for(int i=pos;i;i-=lowbit(i))
			ret=max(ret,ary[i]);
		return ret;
	}
	#undef lowbit
}tary;

int n,m;
char str[N];
int ans[N];
vector< pair<int,int> > qry[N];

int main(){
	// freopen("input.in","r",stdin);
	rin(n),rin(m),scanf("%s",str+1);
	sam.build(str,n);
	sam.solve(n);
	sort(seg+1,seg+1+nseg,cmpSegment);
	// for(int i=1;i<=nseg;i++) printf("[%d,%d] = %d\n",seg[i].le,seg[i].ri,seg[i].key);
	for(int i=1,le,ri;i<=m;i++){
		rin(le),rin(ri);
		qry[ri].push_back(make_pair(le,i));
	}
	tary.init(n);
	for(int i=1,pseg=1;i<=n;i++){
		while(pseg<=nseg && seg[pseg].ri==i){
			tary.modify(n-seg[pseg].le+1,seg[pseg].key);
			pseg++;
		}
		for(int k=0,kk=(int)qry[i].size();k<kk;k++)
			ans[qry[i][k].second]=tary.query(n-qry[i][k].first+1);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

- LCT

点击展开/折叠代码 
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
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int rin(int &r){
	int b=1,c=getchar();r=0;
	while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*=b;
}
const int N=1e5+10;
#define con(type) const type &

struct TreeArray{
	#define lowbit(x) ((x)&(-(x)))
	int arr[N],siz;
	void init(con(int)_siz){siz=_siz;}
	void modify(con(int)pos,con(int)key){
		for(int i=pos;i<=siz;i+=lowbit(i))
			arr[i]=max(arr[i],key);
	}
	int query(con(int)pos){
		int ret=0;
		for(int i=pos;i;i-=lowbit(i)) ret=max(ret,arr[i]);
		return ret;
	}
	#undef lowbit
}tary;

struct Node{
	int nxt[2],len,fa;
	inline int& operator [](con(int)i){return nxt[i];}
};
struct SamAuto{
	Node nod[N<<1];
	int lasnod,rt,ncnt,pos[N];
	int newNode(con(int)_len){
		int p=++ncnt;
		nod[p].len=_len;
		return p;
	}
	void extend(con(int)c,con(int)id){
		int p=lasnod,np=newNode(nod[p].len+1);
		pos[id]=lasnod=np;
		while(p && !nod[p][c]) nod[p][c]=np,p=nod[p].fa;
		if(!p) nod[np].fa=rt;
		else{
			int q=nod[p][c];
			if(nod[q].len==nod[p].len+1) nod[np].fa=q;
			else{
				int nq=newNode(0);
				nod[nq]=nod[q],nod[nq].len=nod[p].len+1;
				nod[np].fa=nod[q].fa=nq;
				while(p && nod[p][c]==q) nod[p][c]=nq,p=nod[p].fa;
			}
		}
	}
	void build(char *str,con(int)len){
		rt=lasnod=newNode(0);
		for(int i=1;i<=len;i++) extend(str[i]-'0',i);
	}
	int operator [](con(int)i){return pos[i];}
}sam;

namespace LCT{
	struct SNode{
		int nxt[2],fa,mx,lzy;
		inline int& operator [](con(int)i){return nxt[i];}
	}nod[N<<1];
	void samToLCT(con(int)n){
		for(int i=1;i<=n;i++)
			nod[i].fa=sam.nod[i].fa;
	}
	bool ifRoot(con(int)u){return !nod[u].fa || (nod[nod[u].fa][0]!=u && nod[nod[u].fa][1]!=u);}
	void setChild(con(int)u,con(int)v,con(int)d){
		nod[u][d]=v;
		if(v) nod[v].fa=u;
	}
	void update(con(int)u,con(int)key){
		nod[u].mx=max(nod[u].mx,key);
		nod[u].lzy=max(nod[u].lzy,key);
	}
	int dir(con(int)x){return nod[nod[x].fa][1]==x;}
	void pushDown(con(int)u){
		if(!nod[u].lzy) return;
		if(nod[u][0]) update(nod[u][0],nod[u].lzy);
		if(nod[u][1]) update(nod[u][1],nod[u].lzy);
		nod[u].lzy=0;
	}
	void pushUp(con(int)u){nod[u].mx=max(nod[u].mx,max(nod[nod[u][0]].mx,nod[nod[u][1]].mx));}
	void ina_rotate(con(int)x){
		int y=nod[x].fa,d=dir(x);
		pushDown(y),pushDown(x);
		if(!ifRoot(y)) setChild(nod[y].fa,x,dir(y));
		else nod[x].fa=nod[y].fa;
		setChild(y,nod[x][!d],d);
		setChild(x,y,!d);
		pushUp(y),pushUp(x);
	}
	void splay(int x){
		static int stk[N<<1];
		int nstk=0,tmp=x;
		while(!ifRoot(tmp))
			stk[++nstk]=tmp,tmp=nod[tmp].fa;
		stk[++nstk]=tmp;
		while(nstk) pushDown(stk[nstk--]);
		while(!ifRoot(x)){
			int y=nod[x].fa;
			if(ifRoot(y)) ina_rotate(x);
			else{
				if(dir(x)==dir(y)) ina_rotate(y);
				else ina_rotate(x);
				ina_rotate(x);
			}
		}
		pushUp(x);
	}
	void access(int x,con(int)tag,con(int)n){
		int y;
		for(y=0;x;y=x,x=nod[x].fa){
			splay(x);
			setChild(x,y,1);
			tary.modify(n-nod[x].mx+1,sam.nod[x].len);
		}
		update(y,tag);
	}
}

int n,m;
char str[N];
int ans[N];
vector< pair<int,int> > qry[N];

int main(){
	// freopen("input.in","r",stdin);
	rin(n),rin(m),scanf("%s",str+1);
	for(int i=1,l,r;i<=m;i++){
		rin(l),rin(r);
		qry[r].push_back(make_pair(l,i));
	}
	tary.init(n);
	sam.build(str,n);
	LCT::samToLCT(sam.ncnt);
	for(int i=1;i<=n;i++){
		LCT::access(sam[i],i,n);
		for(int k=0,kk=(int)qry[i].size();k<kk;k++)
			ans[qry[i][k].second]=tary.query(n-qry[i][k].first+1);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

THE END

Thanks for reading!

（天地虽大）水中明月又一片
（其化均也）心上尘埃只一叶
（万物虽多）提指拈花却一线
（其治一也）恍然一念间
（四达通流）欸乃渔谣隔一涧
（无所不及）跌宕石中叩一焰
（孰守无心）万化兴衰皆成镜鉴
（动以天行）照霜天

——《万象霜天(Vocaloid全员)》By 伊水 / 流绪 / Creuzer

> Link 万象霜天-Bilibili