Logo Universal Online Judge

UOJ

时间限制:4 s 空间限制:1024 MB
统计

题目描述

轨道上有若干地铁,这里我们将地铁抽象为小球,将轨道抽象为数轴。

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

有两种操作:

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

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

按照 $a_i$ 从小到大的顺序($a_i$ 相等时按 $i$ 从小到大的顺序)依次将小球放在数轴上。

第 $i$ 号小球放在 $\leq a_i$ 的没有被之前放置的小球占据的最大的整点处,设第 $i$ 号小球放置的位置为 $b_i$。

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

输入格式

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

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

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

1 i v 表示修改第 i 号小球的坐标参数为 $a_i \leftarrow v$;

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

输出格式

对于每种操作 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,3

下发文件,样例约束与子任务 1 相同。

数据范围

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

  • 子任务 1(10 分):$n, q \leq 10^3$。

  • 子任务 2(10 分):$a_i, v \leq n + 50$。

  • 子任务 3(20 分):没有操作 1。

  • 子任务 4(30 分):每次修改的 $|v − a_i| \leq 1$,即每次修改最多只会让 $a_i$ 改变 $1$。

  • 子任务 5(30 分):无特殊限制。