[Ynoi2019] 魔法少女网站

题目背景

我每天都在想着死去 ![](https://cdn.luogu.com.cn/upload/image_hosting/l47w8gf1.png) 干脆死了算了吧 ![](https://cdn.luogu.com.cn/upload/image_hosting/1r56c7q2.png) 魔法少女网站?这是什么? “真是不幸啊 真是不幸” “给予这样的你——” “魔法的力量吧” ![](https://cdn.luogu.com.cn/upload/image_hosting/x6llyktk.png) 雨谷小雨 唉,自我介绍真麻烦 你因为使用魔杖过度而倒下了,之后就一直没有意识 所以我治好了你 ![](https://cdn.luogu.com.cn/upload/image_hosting/rxxe90qn.png) 在未来的8月11日19时23分 在那一天,tempest将袭来—— Tempest将为这腐朽的世界带来终焉,打开通往新世界的大门 但在这过程中,大多数的人类估计都会死亡 Tempest的到来是不可避免的,但仅有一种方法可以获得救赎—— 那就是填饱王的肚子 王以人类的负能量为食,只要献上这种能量,就能规避tempest带来的死亡 通过使用魔法少女网站给予的魔杖,就能够将负能量储存至魔杖中 只有尽可能多地使用魔杖,比其他魔法少女献上更多的负能量,这样才能成为tempest的赦免对象 如果想活下去,就将充斥着负能量的魔杖,在tempest那天交给我们魔法少女网站吧 最后祝你们迎来美好的终焉 ![](https://cdn.luogu.com.cn/upload/image_hosting/tu991ylc.png) 去掉人类一切的负面情绪 Tempest必将席卷世界 ![](https://cdn.luogu.com.cn/upload/image_hosting/s72vowwk.png)

题目描述

雨谷小雨给你一个长为 $n$ 的序列,定义区间 $[l,r]$ 的子区间为所有形如 $[l',r']$ 的区间,满足 $l',r'$ 为整数,且 $l \le l' \le r' \le r$。 有 $m$ 次操作: `1 x y`:将 $x$ 位置的值修改为 $y$。 `2 l r x`:查询区间 $[l,r]$ 中有多少子区间的最大值小于或等于 $x$。

输入输出格式

输入格式


第一行有两个整数 $n,m$,第二行有 $n$ 个整数表示这个序列。 接下来 $m$ 行,每行形如 `1 x y` 或者 `2 l r x` 表示每次操作。

输出格式


对于每个 $2$ 操作,输出一行一个数表示答案。

输入输出样例

输入样例 #1

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

输出样例 #1

1
1
7
0

说明

Idea:nzhtl1477,Solution:nzhtl1477,Code:ccz181078,Data:ccz181078 对于 $100\%$ 的数据,$n,m \le 3 \times 10^5$,$1 \le l \le r \le n$,$1 \le x, y \le n$,序列中每个元素都在 $[1,n]$ 中,所有数均为整数。