1978. 奶牛过马路
每天，农夫约翰的 N 头奶牛都会穿过农场中间的马路。
考虑约翰的农场在二维平面的地图，马路沿水平方向延伸，马路的一侧由直线 y=0 描述，另一侧由直线 y=1 描述。
奶牛 i 从马路一侧的位置 (ai,0) 沿直线过马路到达另一侧的位置 (bi,1)。
所有 ai 互不相同，所有 bi 互不相同。
尽管他的奶牛们行动敏捷，他还是担心行动路径交叉的两头奶牛在过马路时发生碰撞。
约翰认为，如果一头奶牛的行动路径没有跟其他任何奶牛的行动路径相交，则该奶牛是安全的。
请帮助约翰计算安全奶牛的数量。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含两个整数 ai,bi，用来描述一头牛的行动路径。
输出格式
输出安全奶牛的数量。
数据范围
1≤N≤105,
?106≤ai,bi≤106
输入样例：
4
-3 4
7 8
10 16
3 9
输出样例：
2
样例解释
第一头牛和第三头牛的行动路线不与其他奶牛的路线相交。
第二头牛和第四头牛的行动路线相交。
代码：
// 前缀最值 大于前面序列的最大值 小于后面序列的最小值
#include <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;
const int N = 1e5 + 10;
const int INF = 1e8 + 10;int smin[N], smax[N];
PII q[N];
int res = 0;int main()
{int n;cin >> n;smin[n + 1] = INF, smax[0] = -INF;for (int i = 1; i <= n; i++)cin >> q[i].first >> q[i].second;sort(q + 1, q + n + 1);for (int i = 1; i <= n; i++)smax[i] = max(smax[i - 1], q[i].second);for (int i = n; i >= 1; i--)smin[i] = min(smin[i + 1], q[i].second);for (int i = 1; i <= n; i++){if (q[i].second >= smax[i - 1] && q[i].second <= smin[i + 1])res++;}cout << res;return 0;
}