#P4170. [2015年湖南省队省队集训]极光

    ID: 3385 传统题 1000ms 512MiB 尝试: 384 已通过: 127 难度: 7 上传者: 标签>CF2300提高+/省选-坐标变换二维树状数组离线预收集坐标局部离散化容斥原理杂项

[2015年湖南省队省队集训]极光

题目描述

"若是万一琪露诺(俗称rhl)进行攻击,什么都好,冷静地回答她的问题来吸引她。对方表现出兴趣的话,那就慢慢地反问。在她考虑答案的时候,趁机逃吧。就算是很简单的问题,她一定也答不上来。" --《上古之魔书》

天空中出现了许多的北极光,这些北极光组成了一个长度为nn的正整数数列a[i]a[i]。远古之魔书上记载到:2个位置的graze值为两者位置差与数值差的和:graze(x,y)=∣x−y∣+∣a[x]−a[y]∣\text{graze}(x,y) = |x-y| + |a[x]-a[y]|。 要想破解天罚,就必须支持2种操作(kk都是正整数):

  1. Modify x k:将第xx个数的值修改为kk。
  2. Query x k:询问有几个ii满足graze(x,i)≤k\text{graze}(x,i) \leq k。

由于从前的天罚被圣王lmc破解了,所以rhl改进了她的法术,询问不仅要考虑当前数列,还要考虑任意历史版本,即统计任意位置上出现过的任意数值与当前的a[x]a[x]的graze值≤k\leq k的对数。(某位置多次修改为同样的数值,按多次统计)

输入格式

第1行两个整数n,qn, q。分别表示数列长度和操作数。第2行nn个正整数,代表初始数列。接下来qq行每行一个操作。n≤40000n \leq 40000,修改操作数 ≤60000\leq 60000,询问操作数 ≤10000\leq 10000,Max{a[i]}Max\{a[i]\} (含修改) ≤80000\leq 80000

输出格式

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

输入数据示例

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

输出数据示例

2
3
3