COGS 2479 奇怪的姿势卡♂过去 （bitset+折半）

思路：

此题显然是CDQ套CDQ套树套树

（）

想用一种奇怪的姿势卡过去

就出现了以下解法

5w*5w/8的bitset 　　hiahiahia

但是空间会爆怎么办啊…　　 折半~ 变成5w*2.5w/8完美卡过去

时间会慢很多么 　　　并没有~~完全可以过 甚至比某些姿势不好的树套树快hiahiahia

代码是不是很短~

//By SiriusRen

#include <bitset>

#include <cstdio>

#include <algorithm>

using namespace std;

int n;long long ans;

bitset<25000>b[50000],jy;

struct Node{int a,b,c,id;}node[50000];

bool cmpa(const Node &a,const Node &b){return a.a<b.a;}

bool cmpb(const Node &a,const Node &b){return a.b<b.b;}

bool cmpc(const Node &a,const Node &b){return a.c<b.c;}

inline int rd(){

    int x=0;char p=getchar();

    while(p<'0'||p>'9')p=getchar();

    while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();

    return x;

}

int main(){

    freopen("partial_order.in","r",stdin);

    freopen("partial_order.out","w",stdout);

    scanf("%d",&n);

    register int i;

    for(i=0;i<n/2;i++)b[i]|=jy,jy.set(i);

    for(i=n/2;i<n;i++)b[i]|=jy;

    for(i=0;i<n;i++)node[i].a=rd();

    for(i=0;i<n;i++)node[i].b=rd();

    for(i=0;i<n;node[i].id=i,i++)node[i].c=rd();

    jy.reset();sort(node,node+n,cmpa);

    for(i=0;i<n;i++){b[node[i].id]&=jy;if(node[i].id<n/2)jy.set(node[i].id);}

    jy.reset();sort(node,node+n,cmpb);

    for(i=0;i<n;i++){b[node[i].id]&=jy;if(node[i].id<n/2)jy.set(node[i].id);}

    jy.reset();sort(node,node+n,cmpc);

    for(i=0;i<n;i++){b[node[i].id]&=jy;if(node[i].id<n/2)jy.set(node[i].id);}

    for(i=0;i<n;i++)ans+=b[i].count();

    jy.reset();

    for(i=0;i<n;i++)b[i].reset();

    for(i=n/2;i<n;i++)b[i]|=jy,jy.set(i-n/2);

    jy.reset();sort(node,node+n,cmpa);

    for(i=0;i<n;i++){b[node[i].id]&=jy;if(node[i].id>=n/2)jy.set(node[i].id-n/2);}

    jy.reset();sort(node,node+n,cmpb);

    for(i=0;i<n;i++){b[node[i].id]&=jy;if(node[i].id>=n/2)jy.set(node[i].id-n/2);}

    jy.reset();sort(node,node+n,cmpc);

    for(i=0;i<n;i++){b[node[i].id]&=jy;if(node[i].id>=n/2)jy.set(node[i].id-n/2);}

    for(i=0;i<n;i++)ans+=b[i].count();

    printf("%lld\n",ans);

}