题目描述
有若干个小球放在数轴上,第 i 号小球的坐标参数为 ai。
有两种操作:
-
输入 i,v,修改第 i 号小球的坐标参数为 ai←v;
-
输入 l,r,询问下述内容:
按照 ai 从小到大的顺序(ai 相等时按 i 从小到大的顺序)依次将小球放在数轴上。第 i 号小球放在 ≤ai 的没有被之前放置的小球占据的最大的整点处,设第 i 号小球放置的位置为 bi。
请你输出 ∑i=1,2,…,n,[l,r]⊆[bi,ai](ai+bi) 的值。也即,所有满足 bi≤l,ai≥r 的小球的 ai+bi 之和。
输入格式
从标准输入读入数据。
第一行两个正整数 n,q,分别表示小球个数和操作次数。
第二行 n 个整数 a1,a2,…,an,用空格分隔,表示初始的坐标参数。
接下来 q 行每行是下列两种之一:
-
1 i v 表示修改第 i 个小球的坐标参数为 ai←v;
-
2 l r 表示询问 ∑i=1,2,…,n,[l,r]⊆[bi,ai](ai+bi)。
输出格式
输出到标准输出。
对于每种操作 2,输出一行一个整数表示答案。
样例 1
3 5
5 5 5
2 4 5
2 3 4
1 2 4
2 5 5
2 1 3
17
8
18
0
最开始,三个小球的位置依次为:
- b1=5,a1=5;
- b2=4,a2=5;
- b3=3,a3=5。
修改之后,三个小球的位置依次为:
- b2=4,a2=4;
- b1=5,a1=5;
- b3=3,a3=5。
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
20
10
0
0
20
12
9
见附加文件(点击页面上方「附加文件」按钮下载)。
数据范围与提示
对于所有数据,1≤n≤105,1≤q≤2×105,n<ai,v≤2n,1≤l≤r≤2n。
详细的数据限制及约定如下(留空表示和上述所有数据的约定相同):
子任务编号 |
分值 |
n,q |
特殊性质 |
1 |
10 |
n,q≤1000 |
|
2 |
|
ai,v≤n+50 |
3 |
20 |
没有操作 1 |
4 |
30 |
每次修改的 ∣v−ai∣≤1,即每次修改最多只会让 ai 改变 1。 |
5 |
|