[COGS2479 && COGS2639]高维偏序(CDQ分治,bitset)

COGS2479：四维偏序。

CDQ套CDQ

CDQ:对a分治，对b排序，再对a打标记，然后执行CDQ2

CDQ2:对b分治，对c归并排序，对d树状数组。

 #include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=l; i<=r; i++)

 using namespace std;

 typedef long long ll;

 const int N=;

 int n,ans,c[N];

 struct P{ int a,b,c,d; bool flag; }a[N],t1[N],t2[N];

 void add(int p,int v){ for(;p<=n;p+=p&-p) c[p]+=v;}

 int sum(int p){ int re=; for(;p;p-=p&-p) re+=c[p]; return re; }

 void CDQ2(int l,int r){

     if(l==r) return;

     int mid=(l+r)>>;

     CDQ2(l,mid); CDQ2(mid+,r);

     int i=l,j=mid+,p=l;

     P *a=t1,*t=t2;

     while(i<=mid||j<=r){

         if(j>r||(i<=mid&&a[i].c<a[j].c)){

             if(a[i].flag) add(a[i].d,);

             t[p++]=a[i++];

         }else{

             if(!a[j].flag) ans+=sum(a[j].d);

             t[p++]=a[j++];

         }

     }

     for(int i=l;i<=mid;i++) if(a[i].flag) add(a[i].d,-);

     for(int i=l;i<=r;i++) a[i]=t[i];

 }

 void CDQ(int l,int r){

     if(l==r) return;

     int mid=(l+r)>>;

     CDQ(l,mid);CDQ(mid+,r);

     int i=l,j=mid+,p=l;

     P *t=t1;

     while(i<=mid||j<=r){

         if(j>r||(i<=mid&&a[i].b<a[j].b)) (t[p++]=a[i++]).flag=;

         else (t[p++]=a[j++]).flag=;

     }

     for(int i=l;i<=r;i++) a[i]=t[i];

     CDQ2(l,r);

 }

 int main(){

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

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

     scanf("%d",&n);

     rep(i,,n) scanf("%d",&a[i].b);

     rep(i,,n) scanf("%d",&a[i].c);

     rep(i,,n) scanf("%d",&a[i].d),a[i].a=i;

     CDQ(,n); printf("%d",ans);

     return ;

 }

COGS2639 7维偏序。

每一维记录前面的比当前这一维小的数个数，最后bitset取&就好了。

分块降低时空复杂度，均为$O(kn\sqrt{n})$。

 #include <cstdio>

 #include <cmath>

 #include <bitset>

 #include <algorithm>

 #define rep(i,l,r) for (int i=l; i<=r; i++)

 using namespace std;

 typedef long long ll;

 typedef bitset<>bit;

 const int N=;

 int n,k,size,block[N];

 struct Bitset{

     int a[N],lis[N];

     bit B[];

     bit get(int p){

         p=a[p]; int bp=block[p]; bit ans=B[bp-];

         for(int i=(bp-)*size+;i<p;i++) ans.set(lis[i]);

         return ans;

     }

 }d[];

 void build(int op){

     rep(i,,n) d[op].lis[d[op].a[i]]=i;

     bit t; t.reset();

     rep(i,,n){

         t.set(d[op].lis[i]);

         if(i%size==) d[op].B[i/size]=t;

     }

 }

 int main(){

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

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

     scanf("%d%d",&n,&k); size=sqrt(n);

     rep(i,,n) block[i]=(i-)/size+;

     rep(i,,n) d[].a[i]=i;

     rep(i,,k) rep(j,,n) scanf("%d",&d[i].a[j]);

     rep(i,,k) build(i);

     int ans=;

     rep(i,,n){

         bit t=d[].get(i);

         rep(j,,k) t&=d[j].get(i);

         ans+=t.count();

     }

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

     return ;

 }

更高维的偏序呢？$O(n^2)$暴力吧。