UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2989. 数列

Statistics 下载数据

Description

给定一个长度为n的正整数数列a[i]。
定义2个位置的graze值为两者位置差与数值差的和,即graze(x,y)=|x-y|+|a[x]-a[y]|。
2种操作(k都是正整数):
1.Modify x k:将第x个数的值修改为k。
2.Query x k:询问有几个i满足graze(x,i)<=k。因为可持久化数据结构的流行,询问不仅要考虑当前数列,还要
考虑任意历史版本,即统计任意位置上出现过的任意数值与当前的a[x]的graze值<=k的对数。(某位置多次修改为
同样的数值,按多次统计)

Input

第1行两个整数n,q。分别表示数列长度和操作数。
第2行n个正整数,代表初始数列。
第3--q+2行每行一个操作。

Output

对于每次询问操作,输出一个非负整数表示答案

Sample Input

3 5
2 4 3
Query 2 2
Modify 1 3
Query 2 2
Modify 1 2
Query 1 1

Sample Output

2
3
3

Hint

N<=60000 修改操作数<=40000 询问<=50000 Max{a[i]}含修改<=100000

Source