Home => ProblemSet => 3.11-04:分块二
Problem1796--3.11-04:分块二

1796: 3.11-04:分块二

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 2
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

给出一个长为n的数列，以及m个操作，操作涉及区间加法，询问区间内小于某个值x的元素个数。
操作格式：
1 x y z，表示从x到y每个数加上z
2 x y z，表示查询从x到y的区间内小于z的元素个数

Input

第一行两个正整数n m
第二行n个整数序列
接下来m行操作，含义如题

Output

若干行，每行一个结果，表示小于x的元素的个数

Sample Input Copy 

3 2
1 3 2
1 1 3 1
2 1 3 4

Sample Output Copy 

2

HINT

1 <= n, m <= 20000

Source/Category

算法 模拟 分块 线段树 树状数组 
[ Submit ] [ Status ]