#1826. 赫露艾斯塔

    ID: 1826 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1787来源:qoj.ac数据:公开样例线段树

赫露艾斯塔

赫露艾斯塔

题目描述

标题: 赫露艾斯塔 - Problem - QOJ.ac

#8949. 赫露艾斯塔

Statistics

给定 n 个点 (xi,yi)i=1n,你需要按顺序处理 m 次操作。每次操作给出 o,x,y,X,Y,

  • 首先进行修改:

    • 若 o=1 则将满足 xi≤x,yi≤y 的点的 yi 修改为 y;
    • 若 o=2 则将满足 xi≤x,yi≤y 的点的 xi 修改为 x。
  • 然后进行查询,询问满足 xi≤X,yi≤Y 的点数。

输入格式

第一行两个整数 n,m。

接下来 n 行每行两个整数 xi,yi。

接下来 m 行每行五个整数 o,x,y,X,Y,表示一次操作。

输出格式

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

样例数据

样例输入

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

样例输出

4
3
0
0
0
0

子任务

对于所有数据,1≤n,m≤106,1≤xi,yi,x,y,X,Y≤n。

子任务 1(10 分):n,m≤103;

子任务 2(20 分):xi,yi,x,y,X,Y 独立地在 1 到 n 内均匀随机选取;

子任务 3(20 分):o=1;

子任务 4(20 分):n,m≤3×105,依赖子任务 1;

子任务 5(30 分):无特殊限制,依赖子任务 1、2、3、4。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 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
4
3
0
0
0
0