emmm

Problem

COGS 偏序 / 偏序 II/ 偏序 ++

四维偏序

CDQ 套 CDQ...

对第一维排序，然后对第二维分治递归。

我们要算左边对右边的贡献，于是第二维在某层分治回溯合并完之后，我们可以对第一维重新编号。给左边的第一维设为 0，右边的设为 1，然后第二维已经排序好了，我们再对第三维分治，把重新编号的第一维作为第四维，再把原来的第四维作为第五维用树状数组维护。

似乎更麻烦了？
因为原本我们是想要对后两维树套树来搞的。
但是后两维中的前一维若只为 0 /1，岂不美滋滋？
完全合情合理好嘛。

时间复杂度：$O(n \log^3 n)$

// Code by ajcxsu
// Problem: 4dcdq

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=5e4+10;
struct Node { int b,c,d,e; } a[N], t1[N], t2[N];
ll ans;

int C[N];
#define lowbit(x) x&-x
void updata(int x, int d) {
    while(x<N) {
        C[x]+=d;
        x+=lowbit(x);
    }
}
int query(int x) {
    int ret=0;
    while(x) {
        ret+=C[x];
        x-=lowbit(x);
    }
    return ret;
}

void merge2(int l, int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    merge2(l, mid), merge2(mid+1, r);
    int i=l, j=mid+1, k=l;
    Node *a=t1, *t=t2;
    while(i<=mid && j<=r) {
        if(a[i].c<a[j].c) {
            if(!a[i].e) updata(a[i].d, 1);
            t[k++]=a[i++];
        }
        else {
            if(a[j].e) ans+=query(a[j].d);
            t[k++]=a[j++];
        }
    }
    while(j<=r) {
        if(a[j].e) ans+=query(a[j].d);
        t[k++]=a[j++];
    }
    for(int ni=l;ni<i;ni++) if(!a[ni].e) updata(a[ni].d, -1);
    while(i<=mid) t[k++]=a[i++];
    for(int i=l;i<=r;i++) a[i]=t[i];
}

void merge(int l, int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    merge(l, mid), merge(mid+1, r);
    Node *t=t1;
    int i=l, j=mid+1, k=l;
    while(i<=mid && j<=r) {
        if(a[i].b<a[j].b) a[i].e=0, t[k++]=a[i++];
        else a[j].e=1, t[k++]=a[j++];
    }
    while(i<=mid) a[i].e=0, t[k++]=a[i++];
    while(j<=r) a[j].e=1, t[k++]=a[j++];
    for(int i=l;i<=r;i++) a[i]=t[i];
    merge2(l, r);
}

template<typename T> void gn(T &x) {
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

int main() {
    #ifndef LOCAL
    freopen("partial_order.in", "r", stdin);
    freopen("partial_order.out", "w", stdout);
    #endif
    int n;
    gn(n);
    for(int i=1;i<=n;i++) gn(a[i].b);
    for(int i=1;i<=n;i++) gn(a[i].c);
    for(int i=1;i<=n;i++) gn(a[i].d);
    merge(1, n);
    printf("%lld\n", ans);
    return 0;
}

五维偏序

CDQ 套 CDQ 套 CDQ...
对前两维重新编号。
注意一下若前两维就冲突了，则不产生贡献，不计入讨论。
细节自己想吧（逃

时间复杂度：$O(n\log^4 n)$

// Code by ajcxsu
// Problem: 5dcdq

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=5e4+10;
struct Node { int a,b,c,d,e,f; } a[N], t1[N], t2[N], t3[N];
ll ans;

int C[N];
#define lowbit(x) x&-x
void updata(int x, int d) {
    while(x<N) {
        C[x]+=d;
        x+=lowbit(x);
    }
}
int query(int x) {
    int ret=0;
    while(x) {
        ret+=C[x];
        x-=lowbit(x);
    }
    return ret;
}

void merge3(int l, int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    merge3(l, mid), merge3(mid+1, r);
    int i=l, j=mid+1, k=l;
    Node *a=t2, *t=t3;
    while(i<=mid && j<=r) {
        if(a[i].c<a[j].c) {
            if(a[i].f==0) updata(a[i].d, 1);
            t[k++]=a[i++];
        }
        else {
            if(a[j].f==1) ans+=query(a[j].d);
            t[k++]=a[j++];
        }
    }
    while(j<=r) {
        if(a[j].f==1) ans+=query(a[j].d);
        t[k++]=a[j++];
    }
    for(int ni=l;ni<i;ni++) if(a[ni].f==0) updata(a[ni].d, -1);
    while(i<=mid) t[k++]=a[i++];
    for(int i=l;i<=r;i++) a[i]=t[i];
}

void merge2(int l, int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    merge2(l, mid), merge2(mid+1, r);
    Node *a=t1, *t=t2;
    int i=l, j=mid+1, k=l;
    while(i<=mid && j<=r) {
        if(a[i].b<a[j].b) a[i].f=!a[i].e?0:2, t[k++]=a[i++];
        else a[j].f=a[j].e?1:2, t[k++]=a[j++];
    }
    while(i<=mid) a[i].f=!a[i].e?0:2, t[k++]=a[i++];
    while(j<=r) a[j].f=a[j].e?1:2, t[k++]=a[j++];
    for(int i=l;i<=r;i++) a[i]=t[i];
    merge3(l, r);
}

void merge(int l, int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    merge(l, mid), merge(mid+1, r);
    Node *t=t1;
    int i=l, j=mid+1, k=l;
    while(i<=mid && j<=r) {
        if(a[i].a<a[j].a) a[i].e=0, t[k++]=a[i++];
        else a[j].e=1, t[k++]=a[j++];
    }
    while(i<=mid) a[i].e=0, t[k++]=a[i++];
    while(j<=r) a[j].e=1, t[k++]=a[j++];
    for(int i=l;i<=r;i++) a[i]=t[i];
    merge2(l, r);
}

template<typename T> void gn(T &x) {
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

int main() {
    #ifndef LOCAL
    freopen("partial_order_two.in", "r", stdin);
    freopen("partial_order_two.out", "w", stdout);
    #endif
    int n;
    gn(n);
    for(int i=1;i<=n;i++) gn(a[i].a);
    for(int i=1;i<=n;i++) gn(a[i].b);
    for(int i=1;i<=n;i++) gn(a[i].c);
    for(int i=1;i<=n;i++) gn(a[i].d);
    merge(1, n);
    printf("%lld\n", ans);
    return 0;
}

七维偏序

https://www.cnblogs.com/cjyyb/p/8196312.html
看 FHR 的 ppt...

// Code by ajcxsu
// Problem: kdcdq

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef bitset<40010> bs;
const int N=40010, B=250;
int po[8][N], lis[8][N], n, k;
int pos[N], bl[B], br[B], siz, m;
struct Blo {
    bs sum[B];
    bs get(int k, int x) {
        x=po[k][x]; // 查询编号k该维较小的编号的bitset
        bs ret=sum[pos[x]-1];
        for(int i=bl[pos[x]];i<x;i++) ret.set(lis[k][i]);
        return ret;
    }
} d[8];

void ini(int k) {
    for(int i=1;i<=n;i++) lis[k][po[k][i]]=i; // 编号以维度排序之后得到的结果
    bs t; t.reset();
    for(int i=1;i<=n;i++) {
        t.set(lis[k][i]);
        if(i==br[pos[i]]) d[k].sum[pos[i]]=t;
    }
}

template<typename T> void gn(T &x) {
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

int main() {
    #ifndef LOCAL
    freopen("partial_order_plus.in","r",stdin);
    freopen("partial_order_plus.out","w",stdout);
    #endif
    gn(n), gn(k), siz=sqrt(n);
    m=(n-1)/siz+1;
    for(int i=1;i<=m;i++) bl[i]=(i-1)*siz+1, br[i]=i*siz;
    br[m]=n;
    for(int i=1;i<=k;i++)
    for(int j=1;j<=n;j++) gn(po[i][j]);
    for(int i=1;i<=n;i++) po[0][i]=i, pos[i]=(i-1)/siz+1;
    for(int i=0;i<=k;i++) ini(i);
    ll ans=0;
    for(int i=1;i<=n;i++) {
        bs t=d[0].get(0, i);
        for(int j=1;j<=k;j++) t&=d[j].get(j, i);
        ans+=t.count();
    }
    printf("%lld\n", ans);
    return 0;
}