問題一覧 > 通常問題

No.875 Range Mindex Query

レベル : / AI推定難易度 : 975 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 411
作問者 : beet / テスター : tubuann
お気に入りにしたユーザー ProblemId : 3277 / 自分の提出
問題文最終更新日: 2019-09-07 00:05:58
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 222 (セグメント木コンテスト) (順位表) の他の問題:

Problem Statement

You are given a permutation $A = \{ a_1, a_2, ... , a_N \} \ $ with $N$ elements.

A total of $Q$ queries of the following 2 types are given, so process them in order.

  • $1 \ l \ r$
    • Swap the value of $a_l$ and the value of $a_r$.

  • $2 \ l \ r$
    • Print the value of $\displaystyle \arg \min_{i \in [l, r]} a_i $.
    • Note that this value is uniquely determined since $A$ is a permutation.

Input

$N \ Q$
$a_1 \ a_2 \ \cdots \ a_N$
$query_1$
$query_2$
$\cdots$
$query_Q$

The first line contains an integer $N$ representing the length of the sequence and an integer $Q$ representing the number of queries, in this order, separated by a single-byte space.

The second line contains $N$ integers separated by single-byte spaces, where the $i$-th integer $(1 \le i \le N)$ represents the initial value of $a_i$.

The $i$-th $(1 \le i \le Q)$ of the following $Q$ lines contains the $i$-th query.

Each query is given in one of the following formats:

  • $1 \ l \ r$
  • $2 \ l \ r$

That is, each query takes one of the above forms.


The input consists of $Q + 2$ lines in total and satisfies the following constraints.

  • All input values are integers.
  • $1 \le N, Q \le 10^5$
  • $1 \le a_i \le N \ \ (1 \le i \le N)$
  • $a_i \neq a_j \ \ (i \neq j)$
  • Query 1
    • $1 \le l \lt r \le N$
  • Query 2
    • $1 \le l \le r \le N$
  • There is at least one Query 2.

Output

For each Query 2, print the value of $ \displaystyle \arg \min_{i \in [l, r]} a_i $, separated by newlines.

Sample

Sample 1
Input
3 3
2 1 3
2 1 3
1 2 3
2 1 3
Output
2
3

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