UOJ Logo

NOI.AC

#90. 排列

统计

题目描述

​ 老虎和蒜头是好朋友。

​ 为了锻炼自己的脑力,老虎经常进行一些速算小练习。例如,老虎常常对着一个长度为 $ n $ 的值域为 $ m $ 的序列,反复问自己,这个序列的第 $ [l, r] $ 个元素是否构成了一个广义排列?一个广义排列定义为排序后相邻元素差值恰好为 $ 1 $ 的序列。

​ 当然,蒜头觉得这对于老虎来说实在太容易了。因此蒜头有时会对序列中的元素进行修改。

输入格式

​ 输入的第一行包括两个正整数 $ n, m $ 。

​ 接下来一行包括 $ n $ 个正整数表示初始序列 $ a $ 。

​ 接下来一行一个正整数 $ q $ ,表示询问次数。

​ 接下来 $ q $ 行,每行形如 1 l r 或是 2 x y 的形式,分别表示询问 $ [l, r] $ 和将 $ a_x $ 修改为 $ y $ 。

输出格式

​ 对于每组询问,输出 YESNO 表示你的答案。

样例

样例一

input

5 10
4 4 3 5 7
3
1 2 4
1 1 3
1 1 5

output

YES
NO
NO

样例二

input

3 150
1 1 1
5
2 1 100
2 2 102
1 1 3
2 3 101
1 1 3

output

NO
YES

数据范围及限制

对于 100% 的数据,$ 1 \le n, q, m \le 10^6 $ ,任意时刻序列中元素均在 $ [1, m] $ 之间。

对于 20% 的数据,$ 1 \le n, q \le 3000 $ 。

对于 40% 的数据,$ 1 \le n, q \le 10^5 $ 。

对于另外 20% 的数据,任意时刻序列中元素两两不同。

对于另外 20% 的数据,序列不会发生修改。

时间限制: 1s

空间限制: 512MB

样例数据下载