原题：小Hi的烦恼
原题大意
描述
小Hi从小的一大兴趣爱好就是学习，但是他发现尽管他认真学习，依旧有学神考的比他好。
小Hi在高中期间参加了市里的期末考试，一共五门：语文、数学、英语、物理、化学。
成绩出来之后，小Hi发现有些同学，所有科目都考的比他好，他很烦恼。所以他想知道所有科目都比自己名次靠前的同学的人数。
为了方便，可以认为不存在两个人某一门名次是相同的。
其他同学们也想知道有多少人全面碾压了他们，所以你需要对所有人输出答案。
输入
第一行，一个正整数N(N <= 30000)，表示人数。
接下来N行，每行五个整数，分别表示五门课依次的排名。
输出
输出共N行，每行一个整数，表示答案。
样例输入
4
1 1 2 2 1
2 3 3 3 2
3 2 1 1 3
4 4 4 4 4
样例输出
0
1
0
3
算法分析
这一题主要是bitset的运用，算法题目已经给出了提示：
小Ho：我想用集合的角度去考虑这个问题。对于每一维，比如说X维，我们能通过按X维的坐标排序，不难求出对i点来说X维比i点小的所有点的集合。现在的问题就转化成对点i来说，求出X维，Y维，Z维，Q维，W维分别比i所在那一维小的集合的交的大小。
小Hi：对！你的思路很好。但是集合大小是O(N^2)，如果暴力实现的话时间复杂度就达到了O(N^2)。
小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（这其实是一个不太好做的问题）。
程序代码
这两个版本的时间和消耗的内存差不多。
我的版本
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
bitset<30005> s[30005][5];
struct Rank{
int a,b,c,d,e,id;
}r[30005];
bitset<30005> t;
int n;
bool cmp1(Rank ob1,Rank ob2){
return ob1.a < ob2.a;
}
bool cmp2(Rank ob1, Rank ob2){
return ob1.b < ob2.b;
}
bool cmp3(Rank ob1, Rank ob2){
return ob1.c < ob2.c;
}
bool cmp4(Rank ob1, Rank ob2){
return ob1.d < ob2.d;
}
bool cmp5(Rank ob1, Rank ob2){
return ob1.e < ob2.e;
}
bool cmp6(Rank ob1, Rank ob2){
return ob1.id < ob2.id;
}
int main(){
// freopen("input.txt","r",stdin);
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d%d%d%d%d",&r[i].a,&r[i].b,&r[i].c,&r[i].d,&r[i].e);
r[i].id = i;
}
sort(r+1,r+1+n,cmp1);
t.reset();
for(int i = 1; i <= n; i++)
{
if(i == 1)
{
t[r[i].id] = 1;
continue;
}
s[r[i].id][0] = s[r[i].id][0] | t;
t[r[i].id] = 1;
}
sort(r+1,r+1+n,cmp2);
t.reset();
for(int i = 1; i <= n; i++)
{
if(i == 1)
{
t[r[i].id] = 1;
continue;
}
s[r[i].id][1] = s[r[i].id][1] | t;
t[r[i].id] = 1;
}
sort(r+1,r+1+n,cmp3);
t.reset();
for(int i = 1; i <= n; i++)
{
if(i == 1)
{
t[r[i].id] = 1;
continue;
}
s[r[i].id][2] = s[r[i].id][2] | t;
t[r[i].id] = 1;
}
sort(r+1,r+1+n,cmp4);
t.reset();
for(int i = 1; i <= n; i++)
{
if(i == 1)
{
t[r[i].id] = 1;
continue;
}
s[r[i].id][3] = s[r[i].id][3] | t;
t[r[i].id] = 1;
}
sort(r+1,r+1+n,cmp5);
t.reset();
for(int i = 1; i <= n; i++)
{
if(i == 1)
{
t[r[i].id] = 1;
continue;
}
s[r[i].id][4] = s[r[i].id][4] | t;
t[r[i].id] = 1;
}
for(int i = 1; i <= n; i++)
s[i][0] = s[i][0]&s[i][1]&s[i][2]&s[i][3]&s[i][4];
for(int i = 1; i <= n; i++){
printf("%lld\n", s[i][0].count());
}
return 0;
}
其他版本
#include<bits/stdc++.h>
#define maxn 30050
using namespace std;
int a[maxn][5],b[5][maxn];
bitset<maxn>s[5][maxn],t; //s[i][j]:第i门课排在j-1之前的编号情况
int main(){
// freopen("input.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=0;j<=4;j++){
scanf("%d",&a[i][j]);
b[j][a[i][j]]=i; //第j门课排第a[i][j]名的是编号为i的人
}
}
for(int j=0;j<=4;j++){
s[j][1]=0;
for(int i=2;i<=n;i++){
s[j][i]=s[j][i-1];
s[j][i].set(b[j][i-1]);
}
}
for(int i=1;i<=n;i++){
t=s[0][a[i][0]];
for(int j=1;j<=4;j++){
t&=s[j][a[i][j]];
}
printf("%d\n",t.count());
}
return 0;
}