二维偏序——常见问题解答

本文主要是介绍二维偏序——常见问题解答，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、定义

• 对于每个点i，都可能有另外一些点的x、y坐标均小于等于点i的x、y坐标，这些点的数量即为点i的二维偏序值.
• 在图1中，点A的二维偏序值为1，B的二维偏序值为2，点C的二维偏序值为0.

• 

• 在图2中，点A与点B的二维偏序值均为0.

• 

二、具体过程

• 很多地方都会直接告诉我们：按照第一维排序，再用树状数组处理第二维即可。但是最重要的并不是具体的运行步骤，而是这个方法里真正蕴含的算法设计的思想.
• 为什么要按照第一维排序：对于每个点，显然只有它前面的点（x坐标小于等于该点）的数量有可能（换句话说，x坐标大于该点的那些点是绝对不可能被计入该点的二维偏序值的）被计入该点的二维偏序值.
• 当然了，仅仅按照第一维排序是不能解决这一问题的，因为不能保证每个点前面的点的y坐标都小于等于这个点。换句话说，假设点i前面的某个点的y坐标大于点i的y坐标，那就不应当计入点i的二维偏序值.
• 例如图3，该图中点A、B、C的二维偏序值均为0.

• 

   

• 为什么要使用树状数组：在二维偏序中，通过对每个点关于x坐标排序，我们得到了一个x轴坐标单调递增的点的序列。接下来要解决的问题，是怎么关于点i获取y坐标小于点i的点的数量。由于只有x坐标小于等于点i的点集需要被考虑（原因前面已经提到过，即只有x坐标小于等于点i的x坐标的点集有可能被计入点i的二维偏序值），
• 我们可以从开头到末尾遍历已关于x轴排序每个点，每遍历到一个点，就将这个点的y坐标添加到树状数组中。这样，对于点i，只需要在树状数组中查询y坐标小于等于点i的y坐标的点的数量，即可获取该点的二维偏序值。在具体理解中，我们可以理解为树状数组在其中起到的作用类似一个垂直于y轴的"挡板"（如图4）。换句话说，这里使用的树状数组实际上是关于各个点的y坐标值的，这一点类似值域线段树.

• 

• 类似地，关于x轴的排序也可以理解为垂直于x轴的"挡板"（图5）（只画出了一部分以便于理解）

• 

   

• 由此可知，该二维偏序算法的正确性是由按照时间顺序（实际是x坐标的升序）不断向树状数组加点（实际只加了y坐标）保证的.

 

---

 代码如下（未经过严格测试）：

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int MAXN=1000010;
int maxValue,tr[MAXN];
int lowbit(int x){return x&-x;
}
void add(int x,int k){for(int i=x;i<=maxValue;i+=lowbit(i)){tr[i]+=k;}
}
int sum(int l,int r){int ans=0;for(int i=r;i>0;i-=lowbit(i)){ans+=tr[i];}for(int i=l-1;i>0;i-=lowbit(i)){ans-=tr[i];}return ans;
}
struct Point{int a,b;bool operator <(const Point &another)const{return another.a<a;}
};
int pointCnt=0;
int main(){int n;scanf("%d%d",&n,&maxValue);priority_queue<Point> q;for(int i=1;i<=n;i++){int tmpA,tmpB;scanf("%d%d",&tmpA,&tmpB);Point tmp=Point{tmpA,tmpB};q.push(tmp);}while(!q.empty()){Point nowPoint=q.top();q.pop();int nowValue=nowPoint.b;cout<<sum(1,nowValue)<<endl;add(nowValue,1);}return 0;
}

 

这篇关于二维偏序——常见问题解答的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---