[Ynoi2002] Optimal Ordered Problem Solver

题目描述

给定 $n$ 个点 $(x_i,y_i)_{i=1}^n$,你需要按顺序处理 $m$ 次操作。每次操作给出 $o,x,y,X,Y$, - 首先进行修改: - 若 $o=1$ 则将满足 $x_i\le x,\;y_i\le y$ 的点的 $y_i$ 修改为 $y$; - 若 $o=2$ 则将满足 $x_i\le x,\;y_i\le y$ 的点的 $x_i$ 修改为 $x$。 - 然后进行查询,询问满足 $x_i\le X,\;y_i\le Y$ 的点数。

输入输出格式

输入格式


第一行两个整数 $n,m$。 接下来 $n$ 行每行两个整数 $x_i,y_i$。 接下来 $m$ 行每行五个整数 $o,x,y,X,Y$,表示一次操作。

输出格式


共 $m$ 行,每行一个整数,依次表示每次操作进行的查询的答案。

输入输出样例

输入样例 #1

5 6
1 2
3 1
5 1
3 5
4 4
1 4 2 5 4
1 4 3 5 3
2 3 5 1 3
2 2 3 1 4
1 3 3 1 4
2 5 5 2 1

输出样例 #1

4
3
0
0
0
0

说明

Idea:ccz181078,Solution:ccz181078,Code:ccz181078,Data:ccz181078 对于所有数据,$1 \le n,m \le 10^6$,$1\le x_i,y_i,x,y,X,Y\le n$。 子任务 1(20 分):$n,m\le 10^3$; 子任务 2(20 分):$x_i,y_i,x,y,X,Y$ 独立地在 $1$ 到 $n$ 内均匀随机选取; 子任务 3(20 分):$o=1$; 子任务 4(20 分):$n,m\le 3\times 10^5$,依赖子任务 1; 子任务 5(20 分):无特殊限制,依赖子任务 1、2、3、4。