hihoCoder1513 (小Hi的烦恼)[bitset]

发表于 | 更新于 | | 阅读次数：

题目链接：https://hihocoder.com/problemset/problem/1513

题目大意：给定许多人的五门课排名，询问每个人有多少人所有课的排名都能碾压他。

小Hi：今天我们来解决“五维数点”问题。
小Ho：什么是“五维数点”问题呢？
小Hi：抽象来说，我们现在有n个在五维空间中的点$(X_i,Y_i,Z_i,Q_i,W_i)$。现在对于每个点，我们需要知道所有坐标均比它小的点的数量。
小Ho：这个问题看起来似曾相似，如果是在二维空间中似乎是一个经典的运用线段树解决的题目。
小Hi：对。但是现在是在五维空间中，看起来难度大了很多。
小Ho：我想用集合的角度去考虑这个问题。对于每一维，比如说X维，我们能通过按X维的坐标排序，不难求出对i点来说X维比i点小的所有点的集合。现在的问题就转化成对点i来说，求出X维，Y维，Z维，Q维，W维分别比i所在那一维小的集合的交的大小。
小Hi：对！你的思路很好。但是集合大小是O(N^2)，如果暴力实现的话时间复杂度就达到了O(N^2)。
小Ho：那该怎么办呢？
小Hi：我们想想可以用什么合理的方法来表示集合以此来加快求集合交的操作。
小Ho：我觉得一种比较直观的方法是用一个长度为n的01串，第i位为0表示i不在集合中，1表示i在集合中。
小Hi：不错哟！那你仔细观察一下，求集合的交到底具有什么性质？比如对于n=6,集合{1,4,5}和集合{2,4,5,6}来说，它们的交是{4,5}。
小Ho：集合求交在01串中可以这么看：若两串第i位都是1，则交的串第i位是1，否则第i位就是0。这个例子中两个集合的01串分别为100110,010111。它们的交就是000110，也就是{4,5}。
小Hi：是的。我们把这个问题转化成了对01串的操作。你有没有发现，这其实类似于二进制中”and”的操作。如果我们把01串看成一个二进制的大整数，那么集合求交就变成了对两个大整数做”and”的操作。
小Ho：哈！有道理。但是这看起来复杂度似乎依旧是O(N^2)的。
小Hi：啊！但是你有没有想过，我们可以利用程序语言中的32位整数加速这个”and”，也就是说我们每32位压缩成一个32位整数，这样本来我们需要32次的操作，一下就变成了做一次位运算“并”的操作。所有我们最后的复杂度能优化成O(N^2/32)。
小Ho：原来如此！那具体怎么实现这个“压缩”的过程呢？
小Hi：其实c++/Java已经为我们设计了这样一种数据结构来解决这种问题。它的名字叫bitset/BitSet。它类似于数组，但是你可以直接对其做位运算。bitset中还有一些有用的函数，如count/cardinality可以快速算出二进制中有多少个1（这其实是一个不太好做的问题）。
引用自题目页提式

感觉比较难想到的是单独对于每一维排序后可以直接$O(n)$递推出每个人这一科的排名关系。

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
#include <cstdio>
#include <cstring>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=30009;
bitset<maxn> se1[maxn];
bitset<maxn> se2[maxn];
bitset<maxn> se3[maxn];
bitset<maxn> se4[maxn];
bitset<maxn> se5[maxn];
struct S {
	int a[5];
	int pos;
}stu[maxn];
bool cmp1(S x,S y) {
	return x.a[0]<y.a[0];
}
bool cmp2(S x,S y) {
	return x.a[1]<y.a[1];
}
bool cmp3(S x,S y) {
	return x.a[2]<y.a[2];
}
bool cmp4(S x,S y) {
	return x.a[3]<y.a[3];
}
bool cmp5(S x,S y) {
	return x.a[4]<y.a[4];
}
bool cmp6(S x,S y) {
	return x.pos<y.pos;
}
int main() {
	int n;
	bitset<maxn> tmp;
	scanf("%d",&n);
	for(int i=0;i<n;i++) {
		scanf("%d%d%d%d%d",&stu[i].a[0],&stu[i].a[1],&stu[i].a[2],&stu[i].a[3],&stu[i].a[4]);
		stu[i].pos=i;
	}
	sort(stu,stu+n,cmp1);
	se1[stu[0].pos].reset();
	for(int i=1;i<n;i++) {
		tmp.reset();
		tmp.set(stu[i-1].pos);
		se1[stu[i].pos]=se1[stu[i-1].pos]|tmp;
	}
	sort(stu,stu+n,cmp2);
	se2[stu[0].pos].reset();
	for(int i=1;i<n;i++) {
		tmp.reset();
		tmp.set(stu[i-1].pos);
		se2[stu[i].pos]=se2[stu[i-1].pos]|tmp;
	}
	sort(stu,stu+n,cmp3);
	se3[stu[0].pos].reset();
	for(int i=1;i<n;i++) {
		tmp.reset();
		tmp.set(stu[i-1].pos);
		se3[stu[i].pos]=se3[stu[i-1].pos]|tmp;
	}
	sort(stu,stu+n,cmp4);
	se4[stu[0].pos].reset();
	for(int i=1;i<n;i++) {
		tmp.reset();
		tmp.set(stu[i-1].pos);
		se4[stu[i].pos]=se4[stu[i-1].pos]|tmp;
	}
	sort(stu,stu+n,cmp5);
	se5[stu[0].pos].reset();
	for(int i=1;i<n;i++) {
		tmp.reset();
		tmp.set(stu[i-1].pos);
		se5[stu[i].pos]=se5[stu[i-1].pos]|tmp;
	}
	for(int i=0;i<n;i++) {
		printf("%lu\n",(se1[i]&se2[i]&se3[i]&se4[i]&se5[i]).count());
	}
}