Question

求一算法 ,是关于数组的问题

如题 一个坐标图储存着若干黑点,其它都是白点 求左右上下方向上都有黑点的白点个数 这些点坐标范围[-10亿,+10亿] 黑点个数[0,10万]

Answer 1

1、将所有黑点坐标值离散化。
2、将黑点数据处理为两份：
A、将同列的点连成小线段，即同列中相邻的点连成线段，线段除两个端点外中间不存在黑点，线段可用C(y1,y2,x)表示，其中y1<y2，并按y1值排序。
B、将同行的点连成大线段，即只需将同行中两个最远点相连，其余点均包含在该线段中，线段可用R(x1,x2,y)表示，其中x1<x2，并按y值排序。
3、按y值从小到大逐一处理行大线段，过程中需要两个数据结构：
树状数组ta：ta[x]表示与当前行线段所在直线相交并且两端点不在直线上的列线段数量。
优先队列qu：队列中存放列线段，以y2值小为优先。
另需记录满足条件的白点数的变量cnt，然后，对于每条行线段具体处理步骤：
1）将待处理的列线段中所有满足Cj.y1<Ri.y的列线段入队qu，并且ta[Cj.x]加1。
2）将qu中所有满足Ck.y2<=Ri.y的列线段从qu出队，并且ta[Ck.x]减1。
3）cnt+=树状数组ta中Ri.x1+1到Ri.x2-1的和，即与当前行线段相交的列线段数。
4、处理完所有行线段后cnt即答案。
优先队列的出队和入队都是O(logn)，树状数组的数组元素加减和数组求和也都是O(logn)，具体原理这里就不说了。虽然在处理每条行线段时可能会进行多次列线段的出入队操作，但从全局来看，每条列线段仅会出入队列各一次。
这是我的思路，没有经过代码实践，有问题可再讨论^_^。