并不会正解,此处讲一个可以过此题(而且跑的飞快)的做法。

考虑直接分块,如果对每个块开个 bitset ,这样合并(如果觉得解释的不是很清楚可以点击阅读全文看完整代码 qwq:

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(int l, int r) {
if (bln[l] == bln[r]) {
for (register int i = l; i <= r; i++)
ans.set(a[i]);
} else {
for (register int i = l; i < fst[bln[l] + 1]; i++)
ans.set(a[i]);
for (register int i = fst[bln[r]]; i <= r; i++)
ans.set(a[i]);
for (register int i = bln[l] + 1; i <= bln[r] - 1; i++)
ans |= f[i];
}
}

如果块大小为 $\sqrt n$ ,那么实际上的复杂度是 $\frac {n ^ 2 \sqrt n}{64} $,复杂度其实和暴力差不多。

Dilute: 我™写了个(假)正解分还和暴力一样。

在不会正解的情况下,显然只能考虑在优化分块上做文章。同学基本都是调整块大小为 $7000$ 左右 + 奇技淫巧的卡常通过,此处讲一个不太一样的做法:

考虑使我们的复杂度变的不正确的部分:

1
2
for (register int i = bln[l] + 1; i <= bln[r] - 1; i++)
ans |= f[i];

由于最多会访问到 $\sqrt n$ 个块,复杂度就不能保证。考虑处理出一个 $pre[i][j]$ 数组,表示std::bitset <N> f[i]std::bitset <N> f[i + j - 1] 的异或和。由于空间限制只有 8MB ,我们只能开约 $480$ 个 std::bitset <N> ,就分成 80 个块,预处理的 $j$ 从 $1$ 到 $8$ 即可。

我们的 txc 哥哥还给了一个非常优秀的常数优化:如果一个数在整个序列里只出现了一次,那么他只要在区间内,对答案的贡献肯定为 $1$(不会因为出现和自己值相同的数而减少)。前缀和处理即可,理论可以少掉一半的常数,Orz.

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×