#578. 「LibreOJ NOI Round #2」小球进洞

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

有若干个小球放在数轴上,第 i 号小球的坐标参数为 a_i

有两种操作:

  1. 输入 i,v ,修改第 i 号小球的坐标参数为 a_i\gets v

  2. 输入 l,r ,询问下述内容:

    按照 a_i 从小到大的顺序( a_i 相等时按 i 从小到大的顺序)依次将小球放在数轴上。第 i 号小球放在 \le a_i 的没有被之前放置的小球占据的最大的整点处,设第 i 号小球放置的位置为 b_i

    请你输出 \sum_{i=1,2,\dots , n,[l,r]\subseteq [b_i,a_i]} (a_i+b_i) 的值。也即,所有满足 b_i\le l,a_i\ge r 的小球的 a_i+b_i 之和。

输入格式

从标准输入读入数据。

第一行两个正整数 n,q ,分别表示小球个数和操作次数。

第二行 n 个整数 a_1, a_2, \dots , a_n ,用空格分隔,表示初始的坐标参数。

接下来 q 行每行是下列两种之一:

  1. \mathtt{1\ i\ v} 表示修改第 i 个小球的坐标参数为 a_i\gets v

  2. \mathtt{2\ l\ r} 表示询问 \sum_{i=1,2,\dots , n,[l,r]\subseteq [b_i,a_i]} (a_i+b_i)

输出格式

输出到标准输出。

对于每种操作 \mathtt{2} ,输出一行一个整数表示答案。

样例

样例输入 1

3 5
5 5 5
2 4 5
2 3 4
1 2 4
2 5 5
2 1 3

样例输出 1

17
8
18
0

样例解释 1

最开始,三个小球的位置依次为:

  1. b_1=5, a_1=5
  2. b_2=4, a_2=5
  3. b_3=3, a_3=5

修改之后,三个小球的位置依次为:

  1. b_2=4, a_2=4
  2. b_1=5, a_1=5
  3. b_3=3, a_3=5

样例输入 2

4 10
5 6 7 6
2 5 5
2 4 6
2 5 7
2 5 8
1 1 5
2 5 5
1 2 5
2 6 6
2 4 4
1 3 6

样例输出 2

20
10
0
0
20
12
9

样例 3

见附加文件(点击页面上方「附加文件」按钮下载)。

数据范围与提示

对于所有数据, 1\le n \le 10^5 ,1\le q\le 2\times 10^5 , n< a_i,v \le 2n , 1\le l \le r \le 2n

详细的数据限制及约定如下(留空表示和上述所有数据的约定相同):

子任务编号 分值 n,q 特殊性质
1 10 n,q\leq 1000
2 a_i,v \le n+50
3 20 没有操作 \texttt{1}
4 30 每次修改的 \lvert v - a_i\rvert \le 1 ,即每次修改最多只会让 a_i 改变 1
5