[题解] [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

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