一道 bitset 傻逼题。随便乱搞一下就好了,跑的飞快。

BZOJ5404 - party

和其他题解不太一样,这里没有用线段树……

首先肯定会在 LCA 处集合,通过树剖 + bitset 维护出可选的集合。然后利用 Hall 定理进行完美匹配统计答案。可以发现直接树剖 + 暴力跳是 $O(n ^ 2)$ 的,所以限制树链的长度至多为 $S$ ,则复杂度为:$O(n + qcS\times\frac{m}{32} + qc \times \frac{n}{S} + q \times 2^c \times \frac{m}{32})$ ,取 $S = \sqrt n$ 。

然后跑的飞快 233333.

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

考虑直接分块,如果对每个块开个 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.

bitset 套莫队板子题。

题意是如果第一个区间里有 $ a $ 个 $ x $ ,第二个区间 $ b $ 个,第三个区间 $ c $ 个,只会对答案产生 $ \min(a, b, c) $ 的贡献;每次询问给你三个区间,问你三个区间里能产生这样的贡献的大小。

考虑 bitset 套莫队。通过一个简单的 trick 使得 bitset 既能反映出每种数又能反映出每种数的个数,每个查询就用三个区间的 bitset 的按位并,取结果的 count 。

然而 $ 10^5 $ 个 $ 10^5 $ 的 bitset 会 MLE 。我们把莫队分成三次,只需要三分之一的空间,可以卡进。

看起来这样 $ O(n ^ 2) $ 的复杂度过不了 $ n = 10^5 $ ,但是由于使用了 bitset 的关系,常数只有 1 / 32 ,实际跑的飞快。

Your browser is out-of-date!

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

×