#P16074. [2022国家队训练南京站]黑白点

    ID: 15285 传统题 3000ms 512MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>CF3100NOI/NOI+/CTS二分图建模顶点覆盖二分图匹配排序贪心有序集合交换论证交替路离线查询分治算法CDQ 分治辅助点压缩边深度优先搜索

[2022国家队训练南京站]黑白点

题目描述

平面上给定 nn 个黑点,之后进行 mm 轮操作。每轮操作会加入一个白点。

你需要在每次加入白点后,求出:最少删去多少个黑点和白点,才能使得不存在一对黑点 (x,y)(x,y) 与白点 (x′,y′)(x',y') 满足:

x≤x′,y≤y′.x\le x',\qquad y\le y'.

换句话说,每次操作后,要删除尽量少的点,使得剩余黑点中没有任何一个点同时在某个剩余白点的左下方或重合位置。

输入格式

第一行一个整数 nn,表示黑点个数。

接下来 nn 行,每行两个整数 xi,yix_i,y_i,表示第 ii 个黑点的坐标。

接下来一行一个整数 mm,表示操作轮数。

接下来 mm 行,每行两个整数 xi,yix_i,y_i,表示第 ii 次加入的白点坐标。

输出格式

输出 mm 行,第 ii 行一个整数,表示第 ii 次操作后的答案。

样例一

输入

3
1 1
2 2
3 3
4
1 1
2 2
1 1
4 4

输出

1
2
2
3

数据范围与子任务

子任务 n,m≤n,m\le 特殊性质 分值
1 50 无 13
2 1000 28
3 100000 所有点满足 xi=yix_i=y_i 17
4 无 42

对于所有数据:

1≤n,m≤100000,1≤xi,yi≤109.1\le n,m\le 100000,\qquad 1\le x_i,y_i\le 10^9.