AT_past202107_l.たくさんの最小値

普及+/提高

通过率:0%

AC君温馨提醒

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

题目描述

维护一个长为 nn 的数组 aa。对其进行 qq 次操作。第 ii 次操作输入三个整数 ti,xi,yit_i,x_i,y_i。按如下规则操作:

  • ti=1t_i=1 时:将 axia_{x_i} 的值改为 yiy_i。此时,1≤xi≤n1 \le x_i \le n,0≤yi≤1090 \le y_i \le 10^9。
  • ti=2t_i=2 时:找出 [xi,yi][x_i,y_i] 区间内的最小值,将其记为 pp,输出所有满足以下两个条件的整数 jj:
  • xi≤j≤yix_i \le j \le y_i;

  • aj=pa_j=p。

  • 此时,1≤xi≤yi≤n1 \le x_i \le y_i \le n。

输入格式

第一行为数组长度 nn 和操作次数 qq。1≤n,q≤2×1051 \le n,q \le 2 \times 10^5。

第二行为 nn 个整数,表示数组 aa。0≤ai≤1090\le a_i \le 10^9。

输出格式

对于每个 ti=2t_i=2 的操作,先输出满足条件的 jj 的个数 mm,再按照递增的顺序输出所有满足条件的 jj。相邻两个数之间以单个空格隔开,输出完要换行。保证满足条件的 jj 的总个数不超过 2×1052 \times 10^5。

输入输出样例

  • 输入#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

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

首页