#2190. 黑白点
黑白点
黑白点
题目描述
标题: 黑白点 - Problem - QOJ.ac
#8358. 黑白点
The problem was used in the following contests:
平面上给定 n 个黑点,进行 m 轮操作,每轮加入一个白点。
你需要在每次加点操作后求出:最少删去多少黑点和白点使得不存在黑点 (x,y) 和白点 (x′,y′) 满足 x≤x′,y≤y′。
输入格式
第一行一个整数 n 表示黑点个数。
接下来 n 行每行两个整数 xi,yi 表示第 i 个黑点的坐标。
接下来一行一个整数 m 表示操作轮数。
接下来 m 行每行两个整数 xi,yi 表示第 i 次加入的白点坐标。
输出格式
m 行,每行一个整数表示第 i 次操作后的答案。
样例一
input
3
1 1
2 2
3 3
4
1 1
2 2
1 1
4 4
output
1
2
2
3
数据范围与提示
子任务编号 n,m≤ 特殊性质 分值 1 50 无 13 2 1000 无 28 3 100000 所有点 xi=yi 17 4 100000 无 42
对于所有数据,保证 1≤n,m≤100000,1≤xi,yi≤109。
时间限制:3s
空间限制:512MB
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3
1 1
2 2
3 3
4
1 1
2 2
1 1
4 4
1
2
2
3