「SOL」谢特(LOJ) | Lucky_Glass's Blog
0%

「SOL」谢特(LOJ)

Oh! s**t bi——(屏蔽)


# 题面

给定一个长度为 $n$ 的字符串 $S$ 和正整数数列 $w_1,w_2,\cdots,w_n$。记以第 $i$ 个字符开头的后缀为 $S_i$。

求 $\max\limits_{i\neq j}\{\operatorname{LCP}(S_i,S_j)+(w_i\oplus w_j)\}$,其中 $\oplus$ 为按位异或。

数据规模:$1\le n\le10^5$,$w_i< n$。


# 解析

LCP?能够快速求LCP的——SAM,哈希+二分……SA的height数组?(虽然SAM也能做,但是感觉height数组要清晰一些)

另外,我写的 height[i] 表示的是 sa[i]sa[i+1] 的 LCP,注意一下下标。

我们知道 $LCP(S_i,S_j)$ 就是 rank[i]rank[j] 之间的 height 的最小值。

不妨对 height 数组的每个位置 $i$,考虑计算以 $i$ 处为 height 最小值的一对 $S_i,S_j$ 的 $\max\{w_i\oplus w_j\}$。如何求两个数异或的最大值?Trie树即可。(线性基是求若干个数的异或和)

那么怎么求有哪些 $S_i,S_j$ 以 $i$ 位置为 height 最小值?可以想到用笛卡尔树,按根为区间最小值的方式建出 height 数组的笛卡尔树。

于是可以递归地计算答案——

  • 叶子 $i$ 处答案为 height[i]+(w[i]^w[i+1]),笛卡尔树中有两个串:w[sa[i]],w[sa[i+1]]
  • 非叶子节点 $i$,先考虑计算答案——枚举一棵子树的中的所有串,在另一棵子树的 Trie 树中查答案,取最大值记为 mx,则答案为 height[i]+mx
    但是如果随便选一棵子树枚举其中的所有串,每次复杂度显然会降至 $O(n\log n)$。我们可以“聪明一点”,用启发式的思想,枚举大小较小的一棵子树中的串,在另一棵子树的 Trie 中查,这样总的复杂度就是 $O(n\log^2n)$。
    最后两棵子树的 Trie 合并,该怎么合并怎么合并,至于复杂度:未合并时,Trie 的总点数为 $O(n\log n)$,每次合并的复杂度是合并的点数,每次合并后总点数会减少合并的点数,总复杂度 $O(n\log n)$。

这样就可以在 $O(n\log^2 n)$ 的复杂度内解决。

最后提一句——注意 Trie 树存二进制的叶子节点的深度(在我的实现中叶子深度应为 $-1$)。


# 源代码

解析说起来还很快乐,但是代码好像也不是特别短……

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

const int N=1e5+10;
#define con(type) const type &

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;
}

namespace SA{
int rnk[N<<1],nrnk[N<<1],sa[N<<1],nsa[N<<1],hgt[N];
int bin[N];
void build(char *str,con(int)n){
for(int i=1;i<=n;i++) bin[str[i]-'a']++;
for(int i=1;i<30;i++) bin[i]+=bin[i-1];
for(int i=1;i<=n;i++) sa[bin[str[i]-'a']--]=i;
rnk[sa[1]]=1;
for(int i=2;i<=n;i++){
rnk[sa[i]]=rnk[sa[i-1]];
if(str[sa[i]]!=str[sa[i-1]]) rnk[sa[i]]++;
}
for(int len=1;rnk[sa[n]]<n;len<<=1){
for(int i=1;i<=n;i++) bin[rnk[sa[i]]]=i;
for(int i=n;i>=1;i--)
if(sa[i]>len)
nsa[bin[rnk[sa[i]-len]]--]=sa[i]-len;
for(int i=n-len+1;i<=n;i++)
nsa[bin[rnk[i]]--]=i;
nrnk[nsa[1]]=1;
for(int i=2;i<=n;i++){
nrnk[nsa[i]]=nrnk[nsa[i-1]];
if(rnk[nsa[i]]!=rnk[nsa[i-1]] || rnk[nsa[i]+len]!=rnk[nsa[i-1]+len])
nrnk[nsa[i]]++;
}
swap(rnk,nrnk),swap(sa,nsa);
}
}
void buildHeight(char *str,con(int)n){
for(int i=1,tmp=0;i<=n;i++){
if(tmp) tmp--;
while(str[i+tmp]==str[sa[rnk[i]-1]+tmp]) tmp++;
hgt[rnk[i]]=tmp;
}
}
}

struct SuperDeque{
int ary[N],le,ri;
void clear(){le=1,ri=0;}
void push_back(con(int)x){ary[++ri]=x;}
void pop_back(){ri--;}
void pop_front(){le++;}
int back(){return ary[ri];}
int front(){return ary[le];}
bool empty(){return le>ri;}
}que;

struct Trie{
int nxt[N*20][2],rt[N],ncnt;
int combine(con(int)u,con(int)v){
if(!u || !v) return u|v;
nxt[u][0]=combine(nxt[u][0],nxt[v][0]);
nxt[u][1]=combine(nxt[u][1],nxt[v][1]);
return u;
}
int query(con(int)u,con(int)num){
int ret=0;
for(int dep=16,v=u;~dep;dep--){
int dir=!(num>>dep&1);
if(nxt[v][dir]) v=nxt[v][dir],ret|=(1<<dep);
else v=nxt[v][!dir];
}
return ret;
}
int query(con(int)u,con(int)dep,con(int)num,con(int)v){
if(dep==-1) return query(v,num);
int ret=0;
if(nxt[u][0]) ret=max(ret,query(nxt[u][0],dep-1,num,v));
if(nxt[u][1]) ret=max(ret,query(nxt[u][1],dep-1,num|(1<<dep),v));
return ret;
}
void insert(int &u,con(int)dep,con(int)num){
if(!u) u=++ncnt;
if(dep==-1) return;
insert(nxt[u][num>>dep&1],dep-1,num);
}
int& operator [](con(int)u){return rt[u];}
}tri;

int n,ans;
int val[N],son[N][2];
char str[N];

int dacDFS(con(int)u){
if(!son[u][0] && !son[u][1]){
tri.insert(tri[u],16,val[SA::sa[u]]);
ans=max(ans,tri.query(tri[u],val[SA::sa[u+1]])+SA::hgt[u]);
tri.insert(tri[u],16,val[SA::sa[u+1]]);
return 2;
}
else if(!son[u][0]){
int ret=dacDFS(son[u][1])+1;
ans=max(ans,tri.query(tri[son[u][1]],val[SA::sa[u]])+SA::hgt[u]);
tri.insert(tri[son[u][1]],16,val[SA::sa[u]]);
tri[u]=tri[son[u][1]];
return ret;
}
else if(!son[u][1]){
int ret=dacDFS(son[u][0])+1;
ans=max(ans,tri.query(tri[son[u][0]],val[SA::sa[u+1]])+SA::hgt[u]);
tri.insert(tri[son[u][0]],16,val[SA::sa[u+1]]);
tri[u]=tri[son[u][0]];
return ret;
}
else{
int res0=dacDFS(son[u][0]),res1=dacDFS(son[u][1]);
if(res0<res1) ans=max(ans,tri.query(tri[son[u][0]],16,0,tri[son[u][1]]));
else ans=max(ans,tri.query(tri[son[u][1]],16,0,tri[son[u][0]]));
tri[u]=tri.combine(tri[son[u][0]],tri[son[u][1]]);
return res0+res1;
}
}
int main(){
rin(n),scanf("%s",str+1);
for(int i=1;i<=n;i++) rin(val[i]);
SA::build(str,n),SA::buildHeight(str,n);
for(int i=1;i<n;i++) SA::hgt[i]=SA::hgt[i+1];
// for(int i=1;i<n;i++) printf("! %d\n",SA::hgt[i]);
que.clear();
for(int i=1;i<n;i++){
int las=0;
while(!que.empty() && SA::hgt[que.back()]>SA::hgt[i]){
son[que.back()][1]=las;
las=que.back(),que.pop_back();
}
son[i][0]=las;
que.push_back(i);
}
int las=0;
while(!que.empty()){
son[que.back()][1]=las;
las=que.back(),que.pop_back();
}
// for(int i=1;i<n;i++) printf("%d %d\n",son[i][0],son[i][1]);
dacDFS(las);
printf("%d\n",ans);
return 0;
}

THE END

Thanks for reading!

若你是最悠长的宫音
我是清亮的羽
分离在琴弦的两极 难相遇
纵然是再遥远的距离
也愿与你相依
只等那一曲琴声起 和鸣

——《琴弦上(vocaloid)》By 乐正绫/赤羽/星葵

> Link 琴弦上-Bilibili