分块模板2

分块模板2

题目描述

给出一个长为\(n\)的数列,有\(t\)次操作.

\(op=1\)对应区间同加一个数,\(op=0\)表示查询区间内小于某个值\(x\)的元素个数.

对\(998244353\)取模

输入

第一行包含两个数\(n,t\),表示原始数组的元素个数和操作的个数。

第二行包括\(n\)个数,表示原始数组。

以下\(t\)行,每行格式为\(1\) \(l\) \(r\) \(x\)或者\(0\) \(l\) \(r\) \(x\).

其中第一个数为\(1\)表示加入操作,为\(0\)表示询问操作。

输出

对每个询问操作输出一行,包括一个数,表示该点的值。

样例输入

10 4 
1 5 2 6 7 4 9 3 1 5 
1 1 1 1
0 1 3 10
1 2 3 4
0 2 4 5

样例输出

3
3

提示

25%的数据满足\(1\leq n\), \(m\leq 20\),修改操作不超过\(n\)个
50%的数据满足\(1\leq n\), \(m\leq 1000\), \(1\leq t\leq 10000\)
75%的数据满足\(1\leq n\), \(m\leq 10000\), \(1\leq t\leq 10000\)
100%的数据满足\(1\leq n\), \(m\leq 100000\), \(1\leq t\leq 100000\)


建议

#define mod 998244353

信息

难度
9
分类
分块数据结构 点击显示
标签
递交数
30
已通过
1
通过率
3%
上传者