← 返回题目列表

AtCoder · past202107_l

L. 多个最小值查询

中文机器翻译题面 查看原题

分数: 6 点

警告

2021 年 7 月 17 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

我们有一系列 N 整数 A=(A_1, A_2, \dots ,A_N).
您要处理 Q 查询此序列。在 i-第一个查询,给定 T_i, X_i,和 Y_i,执行如下操作。

  • If T_i = 1:
    替换 A_{X_i} 与 Y_i.
  • If T_i = 2:
    让 p 是其中的最小值 A_{X_i}, \ldots ,A_{Y_i}。列出所有索引 j 这样 X_i \leq j \leq Y_i 和 A_j = p.

约束

  • 1 \leq N, Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • T_i is 1 or 2.
  • 1 \leq X_i \leq N 和 0 \leq Y_i \leq 10^9,如果 T_i=1.
  • 1 \leq X_i \leq Y_i \leq N if T_i=2.
  • 输入中的所有值都是整数。
  • 索引总数 j 拟上市不超过 2 \times 10^5.

输入

输入由标准输入按以下格式给出:

N Q
A_1 A_2 \dots A_N
T_1 X_1 Y_1
T_2 X_2 Y_2
:
T_Q X_Q Y_Q

输出

让 j_1, j_2, \dots , j_M ( j_1 \lt j_2 \lt \dots \lt j_M ) 是要为查询列出的索引 T_i = 2。 然后,按以下格式打印一行:

M j_1 j_2 \dots j_M

您应该打印 Q_2 这样的行,其中 Q_2 是查询的数量 T_i = 2.


示例输入 1

6 7
3 20 3 10 15 10
2 1 6
2 4 5
1 3 10
1 1 1000000000
2 1 6
1 5 0
2 1 6

示例输出 1

2 1 3 
1 4 
3 3 4 6 
1 5