HihoCoder - 1513 bitset处理五维偏序

题意:给出\(n<3e4\)个有序组\((a,b,c,d,e)\),求对第\(i\)个有序组有多少个\(j\)满足\((a_j<a_i,b_j<b_i,c_j<c_i,d_j<d_i,e_j<e_i)\)

五维偏序问题按套路来可以排序+树套树套树套树(打死

然而这是显然连\(O(n^2)\)暴力都不如的

可是题目给4s,\(O(n^2)\)是不可能的,但在神奇的bitset加持下\(O(5*n^2/32)\)的时空复杂度是可以卡过去的!

用bitset表示集合,\(bit[i]:\)如果\(i\)在集合中就设为1,否则0

维护\(bit[i][j]\),表示排在第\(j\)个关键字的第\(i\)名前面的集合状态

如果\(rank[k]<rank[i]\),则置\(bit[i][j][k]=1\)

这里如果是有序的就可以直接利用bitset的\(O(n^2/32)\)构造进行暴力传递

然后对5个关键字的集合求交就可以得出各个答案

#include<bits/stdc++.h>

#include<unordered_set>

#include<unordered_map>

#define rep(i,j,k) for(register int i=j;i<=k;i++)

#define rrep(i,j,k) for(register int i=j;i>=k;i--)

#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])

#define iter(i,j) for(int i=0;i<(j).size();i++)

#define print(a) printf("%lld",(ll)a)

#define println(a) printf("%lld\n",(ll)a)

#define printbk(a) printf("%lld ",(ll)a)

#define IOS ios::sync_with_stdio(0)

using namespace std;

const int MAXN = 3e4+11;

const int oo = 0x3f3f3f3f;

typedef long long ll;

ll read(){

    ll x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int a[MAXN][6],ra[MAXN][6];

bitset<MAXN> bs[MAXN][6],t;

int main(){

    int n;

    while(cin>>n){

        rep(i,0,n) rep(j,1,5) bs[i][j].reset();

        rep(i,1,n) rep(j,1,5) ra[a[i][j]=read()][j]=i;

        rep(i,2,n) rep(j,1,5){

            bs[i][j]=bs[i-1][j];

            bs[i][j][ra[i-1][j]]=1;

        }

        rep(i,1,n){

            t=bs[a[i][1]][1];

            rep(j,2,5) t&=bs[a[i][j]][j];

            println(t.count());

        }

    }

    return 0;

}