#2732. 「JOISC 2016 Day 2」雇佣计划

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Hono

题目描述

题目译自 JOISC 2016 Day2 T1 「雇用計画

JOI 社为了扩大业务而开始了新社员招募。社员有 NN 名候补者,编号从 11NN, 每名候补者有称为评价值的一个确定整数。 评价值高于某一个值的候补者全部都将被聘用, 他们还将分为几个组别。如果 a,b(a<b)a, b(a \lt b) 同时被聘用且 c(acb)c(a \le c\le b) 全部被聘用时,a,ba,b 进入同一组。

你要处理 MM 个查询,查询有以下两种:

  1. 评价值 BjB_j 以上的候补者全部聘用时的组数;
  2. 将候补者 CjC_j 的评价值更新为 DjD_j

输入格式

第一行两个整数 N,MN, M
接下来 NN 行第 ii 行给出候补者评价值的初始值 AiA_i
接下来 MM 行中,第 jj 行有一个整数 TjT_j

  • Tj=1T_j=1 时给出 BjB_j,意义如上;
  • Tj=2T_j=2 时给出 Cj,DjC_j, D_j,意义如上。

输出格式

每行一个整数表示分组个数。

样例

输入样例 1

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

输出样例 1

2
1
2

样例说明 1

第一次查询时,候补者 1,2,41,2,4 被聘用,1,21,2 一组,44 为一组,输出 22
第二次查询将候补者 44 的评价值更新为 11
第三次查询时,候补者 1,21,2 为一组,输出 11
第四次查询时候补者 1,2,31,2,3 一组,55 一组,输出 22

输入样例 2

7 5
13
19
1
15
13
1
19
1 20
1 1
1 6
1 11
1 17

输出样例 2

0
1
3
3
2

输入样例 3

10 5
8
10
15
2
2
8
5
12
11
4
1 5
2 8 4
1 12
2 5 11
1 16

输出样例 3

2
1
0

数据范围与提示

对于全部数据,1N,M2×105,1Ai,Bj,Dj109,1Tj2,1CjN1 \le N,M \le 2\times 10^5,1\le A_i,B_j,D_j\le 10^9,1\le T_j\le 2,1\le C_j\le N,并保证至少有一次查询 Tj=1T_j=1

具体子任务限制及得分情况如下表:

Subtask 限制 分数
11 N,M2000N,M\le 2000 1010
22 Tj=1T_j=1 2020
33 无追加限制 6060