菜王的 blog

提供一个正确的 bitset 做法。

首先可以将冰激凌的数字离散化。

然后发现直接求不能和谐共处的方案数不好求，我们考虑反过来求能和谐相处的个数。

设能与第 $i$ 头奶牛和谐相处的奶牛的个数为 $cnt_i$（包括自己），那要求的答案即为 $\dfrac{n(n - 1) - \sum_{i = 1}^n cnt_i - 1}2$。

我们可以想到对于每种冰激凌开一个大小为 $n$ 的 bitset，记录有哪些奶牛喜欢这种冰激凌，那么 $cnt_i$ 就等于这头奶牛喜欢的五种冰激凌所代表的 bitset 或起来的 $1$ 位数。

然后这样求时间复杂度为 $O(\frac{n^2}w)$，空间复杂度为 $O(\frac{n^2}w)$，无法通过。

我们发现其中有很多的 bitset 都没有存什么东西，浪费了很多空间，所以我们考虑根号分治。

具体来讲，如果一个冰激淋的出现次数 $> \sqrt n$，那么对于这种冰激凌开一个 bitset；否则，代替 bitset，对于这种冰激凌开一个 vector。（也是记录有哪些奶牛喜欢这种冰激凌）

查询时，将对应的 bitset 或起来，再把对应的 vector 里面的奶牛暴力加进去。

单次查询时，处理 bitset 时间复杂度为 $O(\frac nw)$，因为我们限制开了 vector 的冰激凌出现次数 $\le \sqrt n$，vector 暴力添加时间复杂度为 $O(\sqrt n)$，总共为 $O(\frac{n^2}w + n \sqrt n)$。

因为我们限制开了 bitset 的冰激凌至少出现 $\sqrt n$ 次，所以至多会开 $\sqrt n$ 个 bitset，且 vector 最多总共占用 $O(n)$ 的空间，空间复杂度为 $O(n \sqrt n)$。

如果实现优秀甚至可以吊打一大堆大常数 $1 \log$……

代码主体部分：

// 懒惰的作者并没有离散化
// lim 为 sqrt(n)
int n, m, cnt, a[50001][6], t[1000001], id[1000001];
vector<int> v[1000001];
bitset<50001> b[lim + 1], c;
ll ans;
int main(){
	read(n);
	for (int i = 1;i <= n;i ++){
		for (int j = 1;j <= 5;j ++) read(a[i][j]), m = max(m, a[i][j]), t[a[i][j]] ++;
	}
	for (int i = 1;i <= m;i ++){
		if (t[i] > lim) id[i] = ++ cnt;
	}
	for (int i = 1;i <= n;i ++){
		for (int j = 1;j <= 5;j ++){
			if (t[a[i][j]] > lim) b[id[a[i][j]]][i] = 1;
			else v[a[i][j]].push_back(i);
		}
	}
	for (int i = 1;i <= n;i ++){
		c.reset();
		for (int j = 1;j <= 5;j ++){
			if (t[a[i][j]] > lim) c |= b[id[a[i][j]]];
			else {
				for (int x : v[a[i][j]]) c[x] = 1;
			}
		}
		ans += c.count() - 1;
	}
	write(n * (n - 1ll) / 2 - ans / 2);
}