题目描述
现在有 n 个位置,每个位置上有若干个正整数,设第 i 个位置上的第 j 个正整数为 pi,j。
初始时,每个位置上只有一个正整数 ai,即 pi,1=ai。
设目前第 i 个位置有 ui 个数,那么 pi,ui 就是 i 位置上的最后一个数。
定义函数 f(x,y,j),参数为三个下标:
f(x,y,j)=∣x−y∣+∣px,ux−py,j∣.
你需要支持两种操作(k 都是正整数):
Modify x k,表示在第 x 位置最后增加一个数 k;
Query x k,表示询问有几个 i,j 满足 j≤ui,f(x,i,j)≤k,即需要对任意位置上的任意数都计算一遍函数值,判断是否 ≤k。
一个位置上可能多次增加相同的数,需要按多次统计。
输入格式
第一行两个整数 n,q,表示数列长度与操作数;
第二行 n 个正整数,代表每个位置上的初始数。
第 3∼q+2 行,每行一个操作。
输出格式
对于每次询问操作,输出一个非负整数表示答案。
样例 1 输入
3 5
2 4 3
Query 2 2
Modify 1 3
Query 2 2
Modify 1 2
Query 1 1
样例 1 输出
2
3
3
样例 1 解释
对于第一次询问,p2,1=4,p3,1=3 满足。
对于第二次询问,p1,2=3,p2,1=4,p3,1=3 满足。
对于第三次询问,p1,1=2,p1,2=3,p1,3=2 满足。
数据范围
对于所有测试数据,保证:1≤n≤60000,1≤q≤105,任意位置上的任意数都不会超过 105。在查询操作中,有 1≤k≤2×105。
| 测试点 |
n≤ |
q≤ |
特殊性质 |
| 1∼5 |
1000 |
无 |
| 6∼10 |
60000 |
105 |
没有修改操作 |
| 11∼13 |
任意位置上的任意数都不会超过 100 |
| 14∼16 |
10000 |
无 |
| 17∼20 |
60000 |