摘要
Title: 1978. 奶牛过马路
Tag: 排序，前缀最值
Memory Limit: 64 MB
Time Limit: 1000 ms

1978. 奶牛过马路

题意

每天，农夫约翰的 N 头奶牛都会穿过农场中间的马路。
考虑约翰的农场在二维平面的地图，马路沿水平方向延伸，马路的一侧由直线 y=0 描述，另一侧由直线 y=1 描述。
奶牛 i 从马路一侧的位置 $(a_i,0)$ 沿直线过马路到达另一侧的位置 $(b_i,1)$ 。
所有 $a_i$ 互不相同，所有 $b_i$ 互不相同。
尽管他的奶牛们行动敏捷，他还是担心行动路径交叉的两头奶牛在过马路时发生碰撞。
约翰认为，如果一头奶牛的行动路径没有跟其他任何奶牛的行动路径相交，则该奶牛是安全的。

思路

题意翻译过来，就是找没有交点的线段。
首先先将线段按照a排序，之后针对每个直线，必须满足下面两个条件，才不能和别的直线起冲突

此直线的b比前面的直线的b都大，即大于他们的最大值
此直线的b比后面的直线的b都小，即小于他们的最小值

那么就可以做一个前缀最大值和后缀最小值，最后排查每个直线

由于有排序，整个算法复杂度是 $nlogn$ 的

代码

对于写 $Python$ 来说，尽量还是养成写c的习惯

数组开到 $n + 2$

vector留一个0下标不用

'''
Author: NEFU AB-IN
Date: 2022-01-12 21:51:06
FilePath: \ACM\Acwing\1978.py
LastEditTime: 2022-01-13 22:13:08
'''
INF = float('inf')
lst = [0]


class Line(object):
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def __lt__(self, t):
        if self.a != t.a:
            return self.a < t.a
        return self.b < t.b


def solve():
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        lst.append(Line(a, b))
    lst[1:] = sorted(lst[1:])
    smax = [0] * (n + 2)
    smin = [0] * (n + 2)

    smax[0] = -INF
    smin[n + 1] = INF

    for i in range(1, n + 1):
        smax[i] = max(smax[i - 1], lst[i].b)
    for i in range(n, 0, -1):
        smin[i] = min(smin[i + 1], lst[i].b)

    res = 0
    for i in range(1, n + 1):
        if lst[i].b > smax[i - 1] and lst[i].b < smin[i + 1]:
            res += 1
    print(res)


if __name__ == "__main__":
    solve()