Problem

https://www.luogu.org/problemnew/show/P3810

Solution

一道模板题。

我们解决逆序对的方法，在归并排序的时候，对右边的每个值计算左边对右边的贡献。

这个其实就是 CDQ 分治。

算逆序对的归并排序的代码：

// Code by ajcxsu
// Problem: 1dcdq

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

const int N=40010;
int arr[N];
int cac[N];

int ans;

void dfs(int l, int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    dfs(l, mid), dfs(mid+1, r);
    int i=l, j=mid+1, k=l;
    while(i<=mid && j<=r) {
        if(arr[i]<=arr[j]) cac[k++]=arr[i++];
        else cac[k++]=arr[j++], ans+=mid-i+1;
    }
    while(i<=mid) cac[k++]=arr[i++];
    while(j<=r) cac[k++]=arr[j++];
    for(int i=l;i<=r;i++) arr[i]=cac[i];
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    dfs(1,n);
    cout<<ans<<endl;
    return 0;
}

那么我们一维一维地来：

一维偏序

一维偏序是不是排个序就行了？

二维偏序

二维偏序，首先对第一维从小到大排个序，然后用递归算顺序对。
因为递归的区间 $[l,r]$，从 $mid$ 分割出来的左右两个区间，右边区间的第一维坐标一定比左边区间的第一维坐标大。
所以按照算逆序对的思想，算算后面对前面的贡献就行了。也就是对于右边区间的每一个值，算算左边区间有多少个值比它小。

但是这样会出现一个问题：你的排序函数只需要以第一维为关键字吗？否。第二维也需要从小到大排序。

考虑如下一个情况：

i 1 2|3 4 5
x 1 2|2 2 3
y 7 8|3 4 5

如果这个区间从 $2,3$ 之间分隔开来的话，会出现后面应该对前面产生贡献（$(2,3)$ 对 $(2,8)$）的情况，但我们并没有统计这个贡献。
但如果我们以两维来进行排序的话：

i 1 2 3 4 5
x 1 2 2 2 3
y 7 3 4 8 5

我们会发现无论以哪一列进行分隔，都不会有后面对前面产生贡献的情况。

第二个问题，你需要去重。

i 1 2
x 2 2
y 2 2

因为这样子无论怎样都会出现后面对前面产生贡献的情况。

把这两个问题考虑好，二维偏序就简单了。

三维偏序

一维排序。
二维归并。
二路归并的时候算算左边比右边小的坐标中，有多少个的第三维坐标比右边小。这个用树状数组维护就行了。
避免复杂度退化，不要使用memset。

Code

// Code by ajcxsu
// Problem: 3dcdq

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

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

const int N=1e5+10, K=2e5+10;
struct Node {
    int x, y, z, cnt, sum;
} arr[N], b[N];
int ans[N];
bool operator == (const Node &a, const Node &b) { return a.x==b.x && a.y==b.y && a.z==b.z; }
bool cmp(const Node &a, const Node &b) { return a.x==b.x?(a.y==b.y?a.z<b.z:a.y<b.y):a.x<b.x; }

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

void dfs(int l, int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    dfs(l, mid), dfs(mid+1, r);
    int i=l, j=mid+1, k=l;
    while(i<=mid && j<=r) {
        if(arr[i].y<=arr[j].y) b[k++]=arr[i], updata(arr[i].z, arr[i].cnt), i++;
        else {
            arr[j].sum+=query(arr[j].z);
            b[k++]=arr[j++];
        }
    }
    while(j<=r) arr[j].sum+=query(arr[j].z), b[k++]=arr[j++];
    for(int ni=l;ni<i;ni++) updata(arr[ni].z, -arr[ni].cnt);
    while(i<=mid) b[k++]=arr[i++];
    for(int i=l;i<=r;i++) arr[i]=b[i];
}

int main() {
    int n,k;
    gn(n), gn(k);
    int rn=n;
    for(int i=1;i<=n;i++)
        gn(arr[i].x), gn(arr[i].y), gn(arr[i].z), arr[i].cnt=1;
    sort(arr+1, arr+1+n, cmp);
    for(int i=2;i<=n;i++)
        if(arr[i]==arr[i-1]) arr[i].cnt+=arr[i-1].cnt, arr[i-1].x=0x3f3f3f3f;
    sort(arr+1, arr+1+n, cmp);
    while(arr[n].x==0x3f3f3f3f) n--;
    for(int i=1;i<=n;i++) arr[i].sum+=arr[i].cnt-1;
    dfs(1,n);
    int ra[N]={0};
    for(int i=1;i<=n;i++) ra[arr[i].sum]+=arr[i].cnt;
    for(int i=0;i<rn;i++) printf("%d\n", ra[i]);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3810.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆