二维偏序问题是一个常见的模型，有很多方法可以解决，这篇文章总结了一些常见的解法。

• 定义
• 暴力解法
• 数据结构维护
  • 树状数组/线段树
  • Policy-Based Data Structure
• 利用归并排序/归并树

注：本文中的代码是在特定算法竞赛模板下实现的，可以认为是 C++ 风格的伪代码。

定义

给定一个有 $n$ 个元素的集合，其中每个元素有两个属性 $(x_k,y_k)$，求集合中 $x_i<x_j$ 且 $y_i<y_j$ 的 $(i,j)$ 对数。

很多问题都可以化归成二维偏序问题的模型，例如顺序对问题：

给定一个长度为 $n$ 的序列 $a$，求满足 $i<j$ 且 $a_i<a_j$ 的 $(i,j)$ 对数。

以及经典的逆序对问题：

给定一个长度为 $n$ 的序列 $a$，求满足 $i<j$ 且 $a_i>a_j$ 的 $(i,j)$ 对数。

将序列 $a$ 中的所有元素取为相反数，实际上就可以将逆序对问题化归成顺序对问题。

暴力解法

很明显，直接通过二重循环进行统计，很容易得到一个 $O(n^2)$ 的解法：

ll bruteforce(ll n,vpll&a){
    ll ans=0;
    f(i,0,n)f(j,0,i)
        if(a[i].fi<a[j].fi&&a[i].sc<a[j].sc)ans++;
    return ans;
}

如果相等也被包含在偏序关系中，只需要将 if 中的小于号改为小于等于号即可。

但是算法竞赛中 $O(n^2)$ 的解法往往是不可接受的，我们来看看别的方法。

数据结构维护

这类方法往往先使用 $O(n\log n)$ 的时间对第一维 $x_k$ 排序，然后再用数据结构维护第二维 $y_k$，在遍历每个元素的第二维 $y_j$ 时用 $O(\log n)$ 的时间统计目前数据结构中有多少个元素满足 $y_i<y_j$，因此实现在 $O(n\log n)$ 的时间内完成统计。

由于需要先对第一维排序，因此这类方法无论使用在线或离线的数据结构都是离线算法。

树状数组/线段树

维护一个权值为下标的树状数组（也就是维护第二维 $y_k$ 的计数桶），每次统计在本质上就是进行一次 $[\min\{y\},y_k]$ 的区间查询，耗费 $O(\log \max\{y\})$ 的时间，在统计后将 $y_k$ 更新到桶中，本质上就是进行一次 $y_k$ 的单点更新，同样耗费 $O(\log \max\{y\})$ 的时间。

ll sort_with_tree(ll n,vpll&a){
    sort(all(a));
    ll ma=-inf;
    fe(u,a)tmax(ma,u.sc);
    fwi tr(ma);
    ll ans=0;
    fe(u,a){
        ans+=tr.query(u.sc-1);
        tr.update(u.sc,1);
    }
    return ans;
}

其硬伤在于只能维护 $y_k$ 为正整数的情况。如果 $y_k$ 为非正整数，需要根据值域偏移到正整数区间；如果 $y_k$ 的值域过大，则需要先对第二维进行离散化后进行处理，或者在线段树中使用动态开点线段树。

如果相等也被包含在偏序关系中，只需要将 query 中的 u.sc-1 改为 u.sc 即可。

Policy-Based Data Structure

直接使用 PBDS 中支持排名查询的红黑树即可直接在 $O(\log n)$ 时间内进行统计。

ll sort_with_pbds(ll n,vpll&a){
    sort(all(a));
    rbt<ll,nulltype,greater<ll>>tr;
    ll ans=0;
    fe(u,a){
        ans+=tr.order_of_key(u.sc);
        tr.ist(u.sc);
    }
    return ans;
}

实战首选该方法，优点是码量小，无视值域，思路简单粗暴。缺点是常数较大，并且由于其高度封装，难以添加额外功能（假如要额外维护别的东西，比较难修改代码）。

除此之外，如果有第二维有重复元素，可以修改第三个属性为 less_equal 以支持多重集，但是会导致 find 和 erase 方法不可用。更稳妥的方案是将元素改为 pair<int,int>，第一元维护元素值，第二元维护编号，以保证元素不重复，进而能够进行正确的查询。

ll sort_with_pbds(ll n,vpll&a){
    sort(all(a));
    rbt<pll,nulltype,greater<pll>>tr;
    ll ans=0,cnt=0;
    fe(u,a){
        ans+=tr.order_of_key({u.sc,inf});
        tr.ist({u.sc,cnt});
        cnt++;
    }
    return ans;
}

如果相等也被包含在偏序关系中，只需要将 order_of_key 中的 inf 改为 -inf 即可。

利用归并排序/归并树

首先使用 $O(n\log n)$ 的时间对第一维 $x_k$ 排序，然后再对第二维进行归并排序，由于在归并的过程中第一维原本就有序，因此可以借此统计二维偏序。

在归并的某一步时，有两个重要性质：

• 左半部分和右半部分的第二维均有序。
• 对于第一维而言，左半部分的元素总是小于右半部分的元素。

此时可以统计从左半部分和右半部分各选取一个元素后符合的个数。对于右半部分的每个元素，需要找出左半部分中第二维小于它的元素个数。

很显然可以一边合并一边统计：当合并后的数组接下来要加入一个左半部分的元素时，计数器 cnt 自增；要加入一个右半部分的元素时，左半部分的元素中第二维小于它的元素个数正好就是计数器的个数，因此在答案中添加 cnt 即可。

不难发现只要在归并排序的每一步合并都进行统计，最终其和即为二维偏序的对数。

ll solve_merge(ll l,ll r,vpll&a,vpll&t){
    if(l>=r)return 0;
    ll m=l+(r-l)/2,i=l,j=m+1,k=l;
    ll cnt=0,ans=solve_merge(l,m,a,t)+solve_merge(m+1,r,a,t);
    while(i<=m||j<=r){
        if(i<=m&&(j>r||a[i].sc<a[j].sc)){
            t[k++]=a[i++];
            cnt++;
        }else{
            t[k++]=a[j++];
            ans+=cnt;
        }
    }
    f(p,l,r+1)a[p]=t[p];
    return ans;
}
ll merge_sort(ll n,vpll&a){
    sort(all(a));
    vpll t(n);
    return solve_merge(0,n-1,a,t);
}

也可以套用模板先求出归并树，再进行计数，但是空间复杂度会略大。

如果相等也被包含在偏序关系中，只需要将 while 的 if 中的 < 改为 <= 即可。