시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 130 | 6 | 6 | 4.615% |
You may be right that there are a lot (maybe even too many) problems of kind ``given array of length $10^5$ and $10^5$ queries of $10^5$ different types, do some...
- Um_nik
You are given an array $x_1, x_2, \ldots, x_n$.
You need to perform two types of queries on this array.
The first line contains two integers $n,q$ ($1 \leq n,q \leq 500\,000$): the number of elements in the array and the number of queries.
The second line contains $n$ integers $x_1, x_2, \ldots, x_n$ ($1 \leq x_i \leq 10^9$).
Each of the next $q$ lines contains the description of a query.
If the first integer in the line is equal to $1$, then the next two integers are $i$ and $y$ ($1 \leq i \leq n$, $1 \leq y \leq 10^9$), describing a query of the first type.
Otherwise, the first integer in the line is equal to $2$, and the next integer is equal to $l$ ($1 \leq l \leq n$), describing a query of the second type.
For each query of the second type, return the smallest $d$ among all tuples $(a,b,c,d)$ such that $l \leq a < b < c < d$ and $x_a < x_b < x_c < x_d$, or print "-1" if there are no such tuples.
11 10 1 2 3 4 5 10 9 8 7 6 8 2 1 1 3 2 2 1 1 1 2 2 1 2 5 2 6 1 9 6 1 10 7 2 5
4 5 6 -1 -1 11