[题解] [Alpha1022 的无趣比赛] 光棱碎片

[题解] [Alpha1022 的无趣比赛] 光棱碎片

给定字符串 $S$,每一位额外有权值 $v_i$,求有多少对 无序的 本质相同但出现位置不同的子串(右端点分别为 $r_1,r_2$)满足 $L\le (v_{r_1}\oplus v_{r_2})+len\le R$,其中 $L$、$R$ 为给定参数。答案对 $998244353$ 取模。

$1\le |S|,v_i,L,R\le 10^5$

题目链接


思路

所以为什么考场上我盯着甚至已经把 Trie 写好的暴力看了半天都没想到启发式合并()

考虑枚举端点 $r_1,r_2$,然后记 $l$ 为 $|\operatorname{lcp}(S_{1,r_1},S_{1,r_2})|$,这个可以用 SAM 求。然后这对 $r_1,r_2$ 的贡献就是 $\sum_{i=1}^l \left[L-i\le \left(v_{r_1}\oplus v_{r_2}\right)\le R-i\right]$。把 $(v_{r_1}\oplus v_{r_2})$ 的值放到序列 $A$ 上,相当于求了 $A$ 序列的多个区间和,也就是 $A$ 二次前缀和后(记为 $B$)的单点查。具体地,原式即为 $(B_{R}-B_{R-l})-(B_{L-1}-B_{L-l-1})$。然后注意到 $A_i$ 对 $B_j$ 的贡献是 $\max\{j-i+1,0\}$,于是我们就得到了 $O(n^2)$ 做法。

然后考虑启发式合并 $endpos$。于是我们需要维护一个集合 $S$,支持查询对于给定的 $x$ 和 $lim$,$\sum_{v\in S}\max\{lim-v,0\}$ 的值,也就是要维护 $\sum_{v\in S}\left[(v\oplus x)\le lim\right]$ 和 $\sum_{v\in S}(v\oplus x)$ 的值。这个可以用 01 Trie 做到插入查询 $O(\log^2V)$。于是这道题就做完了,时间复杂度 $O(n\log^3n)$。

代码

mivik.h

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
// Mivik 2021.1.16
#include <mivik.h>

#include <cassert>
#include <set>

MI cin;

typedef long long qe;

const int $n = 100005;
const int $lg = 16;
const int $c = 26;
const int mod = 998244353;

inline int add(int x, int y) { return (x += y) >= mod? x - mod: x; }
inline void Add(int &x, int y) { if ((x += y) >= mod) x -= mod; }
inline int sub(int x, int y) { return (x -= y) < 0? x + mod: x; }
inline void Sub(int &x, int y) { if ((x -= y) < 0) x += mod; }

int n, v[$n], lo, hi, ans;

namespace trie {
const int $node = 5000000;
int son[$node][2], cnt[$node], sum[$node][$lg + 1], tot;
inline int build(int v) {
const int ret = ++tot; int x = ret;
auto copy = [&]() {
cnt[x] = 1;
for (int j = 0; j <= $lg; ++j)
sum[x][j] = (v >> j) & 1;
};
copy();
for (int i = $lg; ~i; --i) {
const bool w = (v >> i) & 1;
x = son[x][w] = ++tot;
copy();
}
return ret;
}
int merge(int x, int y) {
if (!(x && y)) return x | y;
const int r = ++tot;
cnt[r] = cnt[x] + cnt[y];
for (int j = 0; j <= $lg; ++j)
sum[r][j] = sum[x][j] + sum[y][j];
son[r][0] = merge(son[x][0], son[y][0]);
son[r][1] = merge(son[x][1], son[y][1]);
return r;
}
inline int sum_of_xor(int x, int v) {
int ret = 0;
for (int i = 0, cur = 1; i <= $lg; ++i) {
int c = sum[x][i]; if ((v >> i) & 1) c = cnt[x] - c;
Add(ret, (qe)cur * c % mod);
Add(cur, cur);
}
return ret;
}
inline std::pair<int, int> xor_lt(int x, int v, int lim) {
assert(lim > 0);
std::pair<int, int> ret = { 0, 0 };
for (int i = $lg; ~i; --i) {
const bool w = (v >> i) & 1;
if ((lim >> i) & 1) {
if (son[x][w]) {
Add(ret.first, cnt[son[x][w]]);
Add(ret.second, sum_of_xor(son[x][w], v));
}
x = son[x][!w];
} else x = son[x][w];
}
return ret;
}
inline int calc(int x, int v, int lim) { // 对所有 t 统计 \sum std::max(lim - (t ^ x), 0)
if (lim <= 0) return 0;
auto [cnt, sum] = xor_lt(x, v, lim);
return sub((qe)cnt * lim % mod, sum);
}
} // namespace trie

namespace sam {
const int $node = $n << 1;
int tar[$node][$c], pre[$node], len[$node], top[$n], seq[$node], rt[$node], nod[$n];
std::set<int> w[$node];
int lst = 1, tot = 1;
inline int node(int l) { len[++tot] = l; return tot; }
inline void extend(int c) {
int i = lst; lst = node(len[i] + 1); w[lst].insert(len[lst]);
nod[len[lst]] = lst;
while (!tar[i][c]) { tar[i][c] = lst; if (!(i = pre[i])) return (void)(pre[lst] = 1); }
const int o = tar[i][c]; if (len[i] + 1 == len[o]) return (void)(pre[lst] = o);
const int s = node(len[i] + 1); memcpy(tar[s], tar[o], sizeof(tar[0]));
pre[s] = pre[o]; pre[lst] = pre[o] = s;
do { tar[i][c] = s; i = pre[i]; } while (i && tar[i][c] == o);
}
inline void merge(int x, int y) {
if (w[x].size() < w[y].size()) {
std::swap(w[x], w[y]);
std::swap(rt[x], rt[y]);
}
for (int pos : w[y]) {
const int v = ::v[pos];
Add(ans, trie::calc(rt[x], v, hi));
Sub(ans, trie::calc(rt[x], v, hi - len[x]));
Sub(ans, trie::calc(rt[x], v, lo));
Add(ans, trie::calc(rt[x], v, lo - len[x]));
w[x].insert(pos);
}
rt[x] = trie::merge(rt[x], rt[y]);
}
inline void solve() {
for (int i = 1; i <= n; ++i) rt[nod[i]] = trie::build(v[i]);
for (int i = 1; i <= tot; ++i) ++top[len[i]];
for (int i = 1; i <= n; ++i) top[i] += top[i - 1];
for (int i = 1; i <= tot; ++i) seq[top[len[i]]--] = i;
for (int i = tot; i > 1; --i) {
const int x = seq[i];
merge(pre[x], x);
}
}
} // namespace sam
int main() {
cin > n; cin.unget(cin.read<char>());
for (int i = 1; i <= n; ++i) sam::extend(cin.get() - 'a');
for (int i = 1; i <= n; ++i) cin > v[i];
cin > lo > hi; --lo;
sam::solve();
cout < ans < endl;
}

[题解] [Alpha1022 的无趣比赛] 光棱碎片

https://mivik.gitee.io/2021/solution/alpha1022-fragment/

作者

Mivik

发布于

2021-01-17

更新于

2022-08-08

许可协议

评论