#CW16. 数点(point)

    ID: 242 传统题 2000ms 512MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>成外联盟2026数据结构树状数组其他离散化

数点(point)

题目描述

现在有 nn 个位置,每个位置上有若干个正整数,设第 ii 个位置上的第 jj 个正整数为 pi,jp_{i,j}。

初始时,每个位置上只有一个正整数 aia_i,即 pi,1=aip_{i,1}=a_i。

设目前第 ii 个位置有 uiu_i 个数,那么 pi,uip_{i,u_i} 就是 ii 位置上的最后一个数。

定义函数 f(x,y,j)f(x,y,j),参数为三个下标:

f(x,y,j)=∣x−y∣+∣px,ux−py,j∣.f(x,y,j)=|x-y|+|p_{x,u_x}-p_{y,j}|.

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

  • Modify x k,表示在第 xx 位置最后增加一个数 kk;
  • Query x k,表示询问有几个 i,ji,j 满足 j≤uij \le u_i,f(x,i,j)≤kf(x,i,j) \le k,即需要对任意位置上的任意数都计算一遍函数值,判断是否 ≤k\le k。

一个位置上可能多次增加相同的数,需要按多次统计。

输入格式

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

第二行 nn 个正整数,代表每个位置上的初始数。

第 3∼q+23 \sim 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=4p_{2,1}=4,p3,1=3p_{3,1}=3 满足。

对于第二次询问,p1,2=3p_{1,2}=3,p2,1=4p_{2,1}=4,p3,1=3p_{3,1}=3 满足。

对于第三次询问,p1,1=2p_{1,1}=2,p1,2=3p_{1,2}=3,p1,3=2p_{1,3}=2 满足。

数据范围

对于所有测试数据,保证:1≤n≤600001 \le n \le 60000,1≤q≤1051 \le q \le 10^5,任意位置上的任意数都不会超过 10510^5。在查询操作中,有 1≤k≤2×1051 \le k \le 2 \times 10^5。

测试点 n≤n \le q≤q \le 特殊性质
1∼51 \sim 5 10001000 无
6∼106 \sim 10 6000060000 10510^5 没有修改操作
11∼1311 \sim 13 任意位置上的任意数都不会超过 100100
14∼1614 \sim 16 1000010000 无
17∼2017 \sim 20 6000060000