世风日下的哗啦啦族I

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

"世风日下啊,女生不穿裙子的太少了"
"这不是社会的进步吗(逃"
"哎,是否可以建立一种结构统计一下各学院各专业各班级女生穿裙子的数量以及裙子的长度"
"然后查询区间裙子最短值?"
"并输出这个区间 穿这个裙子长度的妹子 有多少个?"
"然后判断下在有风的情况下,多少妹子是安全的."


"maya 哗啦啦族真是太可怕啦!"

Input

第一行 n,m表示n个妹子,m个操作
第二行 a1 a2 a3 …… an,n个整数,表示妹子一开始的裙子长度
下面m行:
总共3种操作
1 a b
修改a妹子的裙子,变成b长度
2 l r
查询[l,r]区间的妹子最短的裙子长度,并输出有多少个妹子穿这个长度裙子的
3 l r t
输出[l,r]区间的妹子身穿裙子长度小于等于t的个数
1<=n,m<=50000
1<=a<=n
1<=b<=50000
1<=ai<=50000
1<=l<=r<=n
0<=t<=50000

 

Output

根据询问,输出答案

询问为2 则在一行输出两个整数 a b

询问为3 则只输出一个整数c

 

Sample Input

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

Sample Output

2 1
1

Source

qscqesze

Manager

Information
Solved Number57
Submit Number183
Problem Tags
data structures
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel