#P10633. BZOJ2989 数列/BZOJ4170 极光

BZOJ2989 数列/BZOJ4170 极光

题目描述

给定一个长度为 nn 的正整数数列 aia_i,两个位置的 graze\text{graze} 值为两者位置差与数值差的和:graze(x,y)=xy+axay\text{graze}(x,y)=|x-y|+|a_x-a_y|

你必须支持两种操作(kk 都是正整数):

  • Modify x k,表示将第 xx 个数的值修改为 kk
  • Query x k,表示询问有几个 ii 满足 graze(x,i)k\text{graze}(x,i) \leq k

询问不仅要考虑当前数列,还要考虑任意历史版本,即统计任意位置上出现过的任意数值与当前的 axa_xgraze\text{graze}k\leq k 的对数。(某位置多次修改为同样的数值,按多次统计。)

输入格式

第一行两个整数 n,qn,q,表示数列长度与操作数;

第二行 nn 个正整数,代表初始数列。

3q+23\sim q+2 行,每行一个操作。

输出格式

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

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

提示

对于所有数据,保证 1n6×1041\leq n\leq 6\times 10^411\leq 修改操作数 5×104\leq 5\times 10^411\leq 询问次数 6×104\leq 6\times 10^41ai1\leq a_i 的所有历史版本的最大值 105\leq 10^5