問題一覧 > 通常問題

No.3251 kthmex

レベル : / AI推定難易度 : 3475 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 1
作問者 : trqs / テスター : yukicoder
お気に入りにしたユーザー ProblemId : 12574 / 自分の提出
問題文最終更新日: 2026-11-01 04:12:27
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 480 (Gemini Tester) (順位表) の他の問題:

Remarks

As a first-time experiment, we had Gemini 2.5 Pro act as the tester for this problem.
AI cannot solve this problem.

Problem Statement

Define the $k$ thmex of a set $S$ as the $k$-th term when the positive integers that do not appear in the set $S$ are arranged in ascending order. For a sequence $a_i$ of length $n$, perform the following $m$ operations.
1. Replace all elements whose value is $x$ within the interval $[l,r]$ with $y$.
2. Find the $k$ thmex of the set consisting of the elements contained in the interval $[l,r]$.

Input

$n$ $m$
$a_1\ a_2\ \cdots\ a_n$
(以下 $m$ 行)
$t\ l\ r\ x\ y$    ($t = 1$ のとき)
$t\ l\ r\ k$      ($t = 2$ のとき)

  • $1 \le n,m \le 10^5$
  • $1 \le a_i \le 10^9$
  • $t \in \{1,2\}$
  • $1 \le l \le r \le n$
  • $0 \le x, y \le 10^9$(when $t = 1$)
  • $1 \le k \le 10^9$(when $t = 2$)
  • Output

    For each operation of type $2$, output the $k$ thmex that is the answer to that query, followed by a newline.

    Sample

    Sample 1
    Input
    8 10
    64 64 123 123 123 190 171 97
    1 2 2 64 45
    1 2 2 64 32
    1 1 2 64 76
    1 2 2 64 63
    1 1 2 64 71
    2 1 2 21
    2 1 2 3
    2 2 2 9
    2 2 2 30
    2 2 2 17
    
    Output
    21
    3
    9
    30
    17
    

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。