奶牛过马路（寒假每日一题 9）

每天，农夫约翰的 N N N 头奶牛都会穿过农场中间的马路。

考虑约翰的农场在二维平面的地图，马路沿水平方向延伸，马路的一侧由直线 y = 0 y=0 y=0 描述，另一侧由直线 y = 1 y=1 y=1 描述。

奶牛 i 从马路一侧的位置 ( a i , 0 ) (a_i,0) (ai​,0) 沿直线过马路到达另一侧的位置 ( b i , 1 ) (b_i,1) (bi​,1)。

所有 a i a_i ai​ 互不相同，所有 b i b_i bi​ 互不相同。

尽管他的奶牛们行动敏捷，他还是担心行动路径交叉的两头奶牛在过马路时发生碰撞。

约翰认为，如果一头奶牛的行动路径没有跟其他任何奶牛的行动路径相交，则该奶牛是安全的。

请帮助约翰计算安全奶牛的数量。

输入格式
第一行包含整数 N N N。

接下来 N N N 行，每行包含两个整数 a i , b i a_i,b_i ai​,bi​，用来描述一头牛的行动路径。

输出格式
输出安全奶牛的数量。

数据范围
1 ≤ N ≤ 1 0 5 , − 1 0 6 ≤ a i , b i ≤ 1 0 6 1≤N≤10^5, −10^6≤a_i,b_i≤10^6 1≤N≤105,−106≤ai​,bi​≤106
输入样例：

4
-3 4
7 8
10 16
3 9

输出样例：

2

样例解释
第一头牛和第三头牛的行动路线不与其他奶牛的路线相交。

第二头牛和第四头牛的行动路线相交。

以 a 进行排序（升序）此时，如果 i i i 这条线没有与其他线相交等价于 m a x { b 1 , b 2 , . . . b i − 1 } < b i max { b1,b2,...bi-1 } < bi max{b1,b2,...bi−1} b i min{bi+1,..,bn} > bi min{bi+1,..,bn}>bi所以可以用前缀最大值和后缀最小值实现上述操作

#include
#include

#define x first
#define y second

using namespace std;

typedef pair PII;

const int N = 100010;

PII q[N];
int smax[N], smin[N], INF = 1e8;

int main(){
    
    int n;
    
    scanf("%d", &n);
    
    for(int i = 1; i <= n; i++){
        
        int x, y;
        scanf("%d%d", &x, &y);
        q[i] = {x, y};
    }
    
    sort(q + 1, q + 1 + n);
    
    smax[0] = -INF, smin[n + 1] = INF;
    for(int i = 1; i <= n; i++) smax[i] = max(smax[i - 1], q[i].y);
    for(int i = n; i >= 1; i--) smin[i] = min(smin[i + 1], q[i].y);
    
    int res = 0;
    for(int i = 1; i <= n; i++){
        
        if(q[i].y > smax[i - 1] && q[i].y < smin[i + 1]) res++;
    }
    
    printf("%dn", res);
    
    return  0;
}