Original Number :
Difficulty Level : Medium
Submissions : 526
Asked In :
Marks :15
: 6 | : 3
You are given an array $$$A$$$ consisting of $$$N$$$ continuous natural numbers denoting the seat numbers in a theater. The array values are as follows $$$A = [1, 2, 3, ..., N]$$$.
You have to process $$$Q$$$ queries of two different types:
- type = $$$1$$$ and value = $$$X$$$:
The current seat number $$$X$$$ is occupied now (denoted by 0), and the seat number of all the vacant seats that have current seat numbers greater than $$$X$$$ is decreased by one.
Thus, the enumeration of seats (i.e. current seat numbers at the theater) always remains continuous.
- type = $$$2$$$ and value = $$$X$$$:
Determine the original seat number (seat number before processing any query) of the current seat number $$$X$$$.
Determine the original seat number for each type 2 query in the given order.
The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of testcases. The description of $$$t$$$ testcases follows.
The first line of each testcase contains two space separated integers $$$N$$$ and $$$Q$$$ $$$(1 \le N, Q \le 10^5)$$$ — the number of elements in array $$$A$$$ and the number of queries respectively.
The next $$$Q$$$ lines of each testcase contains two space separated integers $$$type$$$ $$$(1 \le type \le 2)$$$ and $$$X$$$ $$$(1 \le X \le N)$$$ denoting the $$$type$$$ and the value of $$$X$$$ for this query respectively.
It is guaranteed that the sum of $$$N$$$ and $$$Q$$$ over all testcases does not exceed 1e5 respectively and that there are atleast $$$X$$$ elements in $$$A$$$ for each query.
For each testcase, print the answer to each query of type $$$2$$$ in a single line.
2 6 5 2 3 1 3 2 3 1 2 2 4 5 5 1 2 1 1 2 1 1 2 2 2
3 4 6 3 5
For sample test case 1,
Initially, $$$A = [1, 2, 3, 4, 5, 6]$$$ (all seats are vacant)
- In the 1st query, the original seat number at the current seat number 3 is 3.
- After processing the 2nd query, $$$A = [1, 2, 0, 3, 4, 5]$$$ (0 denotes an occupied seat).
- In the 3rd query, the original seat number at the current seat number 3 was 4.
- After processing the 4th query, $$$A = [1, 0, 0, 2, 3, 4]$$$ (0 denotes an occupied seat).
- In the 5th query, the original seat number at the current seat number 4 was 6.
Therefore, the answer is $$$[3, 4, 6].$$$
For sample test case 2,
Initially, $$$A = [1, 2, 3, 4, 5]$$$ (all seats are vacant)
- After processing the 1st query, $$$A = [1, 0, 2, 3, 4]$$$ (0 denotes an occupied seat).
- After processing the 2nd query, $$$A = [0, 0, 1, 2, 3]$$$ (0 denotes an occupied seat).
- In the 3rd query, the original seat number at the current seat number $$$1$$$ was $$$3$$$.
- After processing the 4th query, $$$A = [0, 0, 1, 0, 2]$$$ (0 denotes an occupied seat).
- In the 5th query, the original seat number at the current seat number $$$2$$$ was $$$5$$$.
