No.875 Range Mindex Query
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
beet
tubuann