AT_abc342_g.[ABC342G] Retroactive Range Chmax

省选/NOI-

通过率：0%

AC君温馨提醒

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

题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ 。

请依次处理 $Q$ 个操作。操作有以下三种类型之一：

类型 $1$ 的操作由整数三元组 $(l,r,x)$ 表示，对 $i=l,l+1,\ldots,r$ ，将 $A_i$ 替换为 $\max\{A_i,x\}$ 。
类型 $2$ 的操作由整数 $i$ 表示，撤销第 $i$ 次操作（保证第 $i$ 次操作是类型 $1$ ，且此前未被撤销）。此时数列 $A$ 应为从初始状态出发，依次执行所有未被撤销的类型 $1$ 操作后的结果。
类型 $3$ 的操作由整数 $i$ 表示，输出当前 $A_i$ 的值。

输入格式

输入按以下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $Q$ $\operatorname{query}_1$ $\operatorname{query}_2$ $\vdots$ $\operatorname{query}_Q$

其中， $\operatorname{query}_k\ (1\leq k\leq Q)$ 表示第 $k$ 次操作，具体格式如下：

对于类型 $1$ 的操作：

$1$ $l$ $r$ $x$

表示第 $k$ 次操作为 $(l,r,x)$ 的类型 $1$ 操作。

对于类型 $2$ 的操作：

$2$ $i$

表示第 $k$ 次操作为 $i$ 的类型 $2$ 操作。

对于类型 $3$ 的操作：

$3$ $i$

表示第 $k$ 次操作为 $i$ 的类型 $3$ 操作。

输出格式

设所有类型 $3$ 操作的个数为 $q$ ，请输出 $q$ 行。第 $i$ 行（ $1\leq i\leq q$ ）输出第 $i$ 个被输入的类型 $3$ 操作所要求的值。

输入输出样例

输入#1

6
2 7 1 8 2 8
15
3 1
3 3
3 4
1 1 5 4
3 1
3 3
3 4
1 3 6 9
3 1
3 3
3 4
2 4
3 1
3 3
3 4

输出#1

输入#2

24
721 78 541 256 970 478 370 467 344 542 43 166 619 17 592 222 983 729 338 747 62 452 815 838
35
3 10
3 8
3 8
3 13
3 9
1 1 17 251
3 3
3 19
3 13
3 22
3 1
3 15
3 18
3 10
3 15
1 16 19 883
1 8 23 212
3 5
3 13
2 6
3 15
1 5 18 914
2 17
3 20
1 23 23 56
3 13
2 25
3 13
3 13
3 10
2 16
1 17 22 308
3 19
3 17
3 7

输出#2

说明/提示

数据范围

$1\leq N\leq 2\times 10^5$
$1\leq A_i\leq 10^9\ (1\leq i\leq N)$
$1\leq Q\leq 2\times 10^5$
对于类型 $1$ 操作， $1\leq l\leq r\leq N$ 且 $1\leq x\leq 10^9$
对于类型 $2$ 操作， $i$ 不超过此前操作次数且 $1\leq i$
对于类型 $2$ 操作，第 $i$ 次操作为类型 $1$
对于类型 $2$ 操作， $i$ 不会重复
对于类型 $3$ 操作， $1\leq i\leq N$
所有输入均为整数

样例说明 1

初始时，数列 $A$ 为 $(2,7,1,8,2,8)$ 。第 $1,2,3$ 次操作分别输出 $A_1,A_3,A_4$ 的值，即 $2,1,8$ 。第 $4$ 次操作将 $A_1,A_2,A_3,A_4,A_5$ 替换为 $\max\{A_i,4\}$ 。操作后， $A$ 变为 $(4,7,4,8,4,8)$ 。第 $5,6,7$ 次操作分别输出此时 $A_1,A_3,A_4$ 的值，即 $4,4,8$ 。第 $8$ 次操作将 $A_3,A_4,A_5,A_6$ 替换为 $\max\{A_i,9\}$ 。操作后， $A$ 变为 $(4,7,9,9,9,9)$ 。第 $9,10,11$ 次操作分别输出此时 $A_1,A_3,A_4$ 的值，即 $4,9,9$ 。第 $12$ 次操作撤销第 $4$ 次操作。操作后， $A$ 变为 $(2,7,9,9,9,9)$ 。第 $13,14,15$ 次操作分别输出此时 $A_1,A_3,A_4$ 的值，即 $2,9,9$ 。

由 ChatGPT 4.1 翻译

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

首页