题目详情题解（0）讨论（0）提交记录（0）

AT_abc432_e.[ABC432E] Clamp

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 NN 的整数序列 A=(A1,A2,…,AN)A=(A_1, A_2, \dots, A_N)。

有 QQ 个查询，需要按顺序处理。每个查询有以下两种格式之一：

  • 1 x y：将 AxA_x 的值改为 yy。
  • 2 l r：求 ∑1≤i≤Nmax⁡(l,min⁡(r,Ai))\displaystyle \sum_{1\leq i\leq N} \max(l, \min(r, A_i)) 的值。

输入格式

输入从标准输入读入，格式如下：

N QN\ Q

A1 A2 … ANA_1\ A_2\ \dots\ A_N

query1\text{query}_1

query2\text{query}_2

$\vdots\ $

queryQ\text{query}_Q

这里，queryi (1≤i≤Q)\text{query}_i\ (1\leq i\leq Q) 表示第 ii 个查询，格式为以下之一：

1 x y1\ x\ y

2 l r2\ l\ r

输出格式

设 KK 为第二种类型查询的个数。输出共 KK 行，第 ii 行（1≤i≤K1\leq i\leq K）为第 ii 个第二种类型查询的答案。

输入输出样例

  • 输入#1

    3 4
4 3 2
1 1 7
2 3 5
1 2 0
2 4 2

    输出#1

    11
12

  • 输入#2

    8 10
320 578 244 604 145 839 156 857
2 400 556
1 5 168
2 254 62
2 145 301
1 1 23
1 3 0
2 413 758
2 297 613
1 8 451
2 598 692

    输出#2

    3824
2032
2073
4350
3596
4884

说明/提示

样例解释 1

初始时 A=(4,3,2)A=(4,3,2)。

  • 第一个查询：将 A1A_1 改为 77，AA 变为 (7,3,2)(7,3,2)。
  • 第二个查询：输出 max⁡(3,min⁡(5,7))+max⁡(3,min⁡(5,3))+max⁡(3,min⁡(5,2))=5+3+3=11\max(3, \min(5, 7))+\max(3, \min(5, 3))+\max(3, \min(5, 2))=5+3+3=11。
  • 第三个查询：将 A2A_2 改为 00，AA 变为 (7,0,2)(7,0,2)。
  • 第四个查询：输出 max⁡(4,min⁡(2,7))+max⁡(4,min⁡(2,0))+max⁡(4,min⁡(2,2))=4+4+4=12\max(4, \min(2, 7))+\max(4, \min(2, 0))+\max(4, \min(2, 2))=4+4+4=12。

数据范围

  • 1≤N≤5×1051 \leq N \leq 5\times 10^5
  • 1≤Q≤2×1051 \leq Q \leq 2\times 10^5
  • 0≤Ai≤5×1050 \leq A_i \leq 5\times 10^5
  • 对于第一种类型的查询，
    • 1≤x≤N1 \leq x \leq N
    • 0≤y≤5×1050 \leq y \leq 5\times 10^5
  • 对于第二种类型的查询，
    • 0≤l,r≤5×1050 \leq l,r \leq 5\times 10^5
  • 所有输入均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页