hiho147周 – 数据结构 bitset

题目链接

n个5维数，对于每个数，输出小于他的数的个数(每个维度都比他小);

#include <cstdio>
#include <cstring>
#include <bitset>
#include <vector>
#include <algorithm>
using namespace std;
const int N = ;
struct Node{
    int id;
    int a,b,c,d,e;
    static bool sortByA(const Node &x,const Node &y){
        return x.a<y.a;
    }
    static bool sortByB(const Node &x,const Node &y){
        return x.b<y.b;
    }
    static bool sortByC(const Node &x,const Node &y){
        return x.c<y.c;
    }
    static bool sortByD(const Node &x,const Node &y){
        return x.d<y.d;
    }
    static bool sortByE(const Node &x,const Node &y){
        return x.e<y.e;
    }
};
vector<Node> data[];
bitset<N> bs[N][];
int n;
int main(){
    for(int i=;i<;i++) data[i].resize(N);
    scanf("%d",&n);
    for(int i=;i<n;i++){
        Node tmp;
        scanf("%d%d%d%d%d",&tmp.a,&tmp.b,&tmp.c,&tmp.d,&tmp.e);
        tmp.id = i;
        for(int j=;j<;j++)
            data[j][i] = tmp;
    }
    std::sort(data[].begin(),data[].begin()+n,Node::sortByA);
    std::sort(data[].begin(),data[].begin()+n,Node::sortByB);
    std::sort(data[].begin(),data[].begin()+n,Node::sortByC);
    std::sort(data[].begin(),data[].begin()+n,Node::sortByD);
    std::sort(data[].begin(),data[].begin()+n,Node::sortByE);
    for(int j=;j<;j++){
        bitset<N> curstate;
        curstate.set(data[j][].id);
        for(int i=;i<n;i++) {
            int curId = data[j][i].id;
            bs[curId][j]|=curstate;
            curstate.set(curId);
        }
    }
    for(int i=;i<n;i++){
        for(int j=;j<;j++) bs[i][]&=(bs[i][j]);
        printf("%d\n",bs[i][].count());
    }
    return ;
}