1371: B谍战情报
内存限制：4 MB
时间限制：1.000 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：4
通过：2
题目描述
你深知战场上情报优势不在自己的黑暗，于是早已提前制作了一个工具从机房的网络交换机上获取网络情报，它可以实时获取机房里每个人进行机惨的几率，精确到0.1%。你已经使用了空间压缩技术把机房战场转化成了一条序列，序列上的元素表示这个人进行机惨的几率，现在你想知道某一片战场的平静程度，即这个序列中区间[l, r]里有多少个人的机惨几率不大于某个数。同时因为是实时战场数据，每个人机惨的几率是会变化的，即会若干次修改一个人的几率。
简化题意：给定一个序列，每次求区间小于某数的数的个数，或把一个数改成另一个数。
输入格式
第一行两个数 n, m，表示机房地形转化成序列后的长度和操作个数。
第二行 n 个整数 pi ,表示位置为 i 的人机惨的概率为 
。
。
接下来 m 行每行第一个为整数 op ,若 op 为1则后面有两个整数x, y，表示把 x 位置上的概率改成 
，为2则后面有三个整数l, r, y表示查询区间[l, r]里概率小于
的有几个位置。
，为2则后面有三个整数l, r, y表示查询区间[l, r]里概率小于的有几个位置。
输出格式
对每个 op 为2的询问输出一行一个整数表示答案。
输入样例 复制
10 10
4 8 4 7 8 8 7 2 1 8
1 1 4
1 10 3
1 7 8
2 6 7 4
2 5 9 3
1 2 1
2 1 9 4
1 5 4
2 2 5 7
2 6 7 3输出样例 复制
0
2
3
3
0数据范围与提示
对10%的数据保证 n ≤ 103, m ≤ 103。
对另外20%的数据保证 op = 2。
对100%的数据保证 n ≤ 105, m ≤ 104, pi, y ≤ 103, x, l, r ∈[l, n]。