明理书包

文章
4
资源
0
加入时间
2年10月24天

hdu 5862 Counting Intersections 【线段树/树状数组+离散化】

线段树/树状数组+离散化,题目比较特殊,首先对x坐标进行离散化,然后将平行于y轴的线段拆分成两个点,按y坐标分。再按y坐标大小排序,遇到平行于x轴的查询区间x1到x2的大小即为交点数,遇到平行y轴的线段,如果是某条线段y坐标小的点,线段树上x1点+1,否则x1点-1。自己写的时候,离散化的数组忘记排序以及线段树的大小考虑错了导致超时。/* ******************************