#2190. 黑白点

    ID: 2190 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1646来源:qoj.ac数据:公开样例线段树

黑白点

黑白点

题目描述

标题: 黑白点 - Problem - QOJ.ac

#8358. 黑白点

Statistics

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