ILKQUERYIII - I LOVE Kd-TREES III
The "I-Love-Kd-trees'' annual con is receiving too many applicants so they decided to complicate a bit the task used to select participants. (They realized some people were using other data structures to solve their problems, so they designed this problem, almost only solvable with Kd-trees).
You are given a list of N numbers and Q queries. Each query can be of two types.
- Type-0 queries (marked with 0 in the input), consist of three integers: i, l and k ; let d be the k-th smallest element until the index i (i.e. if the first i +1 elements were sorted in non-descending way, d would be the element at index k - 1). Then, the answer to each query is the index of the l-th occurrence of d in the array. If there's no such index, the answer is -1.
- Type-1 queries (marked with 1 in the input) are contiguous-swap update-queries, and consists of a single integer i. When a type-1 query is executed the elements at index i and i +1 in the list must be swapped.
You have to consider that all indexes are counted starting with 0.
Input
Input consists of one test case.
The first line contains two integers, N (1 ≤ N ≤ 106) and Q (1 ≤ Q ≤ 105).
The next line contains N possible distinct integers ai (-109 ≤ ai ≤ 109).
Then Q lines follow. Each of them starts with an integer which can be 0 or 1, denoting the type of the query. If it’s 0, then three integers i, l and k follow (0 ≤ i < N, 1 ≤ k ≤ i+1, 1 ≤ l ≤ N).
If it’s 1, then an integer i follows, meaning that you have to swap the elements at indexes i and i+1 (0 ≤ i ≤ N-1).
Output
For each query of type-0 (in the same order as the input) output a single line with the answer to that query.
Example
Input: 10 6
2 3 1 1 2 7 9 1 2 6
0 2 3 2
1 1
1 2
0 2 3 2
1 0
0 0 2 1
Output: 8
7
2
hide comments
treenipples:
2021-05-13 21:25:22
Ignoring type-1 queries with i=n-1 results in AC. Not ignoring results in runtime error. |
|
DK...:
2019-05-07 23:41:50
@BerSub what we suppose to do with type 1 queries in which i=n-1? |
|
Ankit Sultana:
2017-09-08 16:28:06
There are test cases with i = n - 1 for Type 1 Queries, which doesn't make any sense. |
|
mahmud2690:
2016-12-14 07:22:55
As there is a problem with the input, for the 1-type queries there cases I = N - 1. |
|
Rishav Goyal:
2016-08-17 11:08:09
will it pass O(Q(logn)^2) ? |
|
bsubercaseaux:
2016-03-25 22:49:10
Ready ! :-P |
|
[Rampage] Blue.Mary:
2016-03-25 15:49:03
Where's the example Input/Output? |
Added by: | BerSub |
Date: | 2016-03-25 |
Time limit: | 0.400s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |