Inverse Inversions
Contest: Codeforces Round 728 (Div. 1)
Difficulty rating: 3200
Tags: binary search, brute force, data structures

You were playing with permutation $$$p$$$ of length $$$n$$$, but you lost it in Blair, Alabama!

Luckily, you remember some information about the permutation. More specifically, you remember an array $$$b$$$ of length $$$n$$$, where $$$b_i$$$ is the number of indices $$$j$$$ such that $$$j < i$$$ and $$$p_j > p_i$$$.

You have the array $$$b$$$, and you want to find the permutation $$$p$$$. However, your memory isn't perfect, and you constantly change the values of $$$b$$$ as you learn more. For the next $$$q$$$ seconds, one of the following things happen:

1. $$$1$$$ $$$i$$$ $$$x$$$ — you realize that $$$b_i$$$ is equal to $$$x$$$;
2. $$$2$$$ $$$i$$$ — you need to find the value of $$$p_i$$$. If there's more than one answer, print any. It can be proven that there's always at least one possible answer under the constraints of the problem.

Answer the queries, so you can remember the array!

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the size of permutation.

The second line contains $$$n$$$ integers $$$b_1, b_2 \ldots, b_n$$$ ($$$0 \leq b_i < i$$$) — your initial memory of the array $$$b$$$.

The third line contains a single integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — the number of queries.

The next $$$q$$$ lines contain the queries, each with one of the following formats:

- $$$1$$$ $$$i$$$ $$$x$$$ ($$$0 \leq x < i \leq n$$$), representing a query of type $$$1$$$.
- $$$2$$$ $$$i$$$ ($$$1 \leq i \leq n$$$), representing a query of type $$$2$$$.

It is guaranteed that there's at least one query of type $$$2$$$.

Output format:
For each query of type $$$2$$$, print one integer — the answer to the query.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
For the first sample, there's initially only one possible permutation that satisfies the constraints: $$$[1, 2, 3]$$$, as it must have $$$0$$$ inversions.

After the query of type $$$1$$$, the array $$$b$$$ is $$$[0, 1, 0]$$$. The only permutation $$$p$$$ that produces this array is $$$[2, 1, 3]$$$. With this permutation, $$$b_2$$$ is equal to $$$1$$$ as $$$p_1 > p_2$$$.

Example input:
3
0 0 0
7
2 1
2 2
2 3
1 2 1
2 1
2 2
2 3

Example output:
1
2
3
2
1
3

Example input:
5
0 1 2 3 4
15
2 1
2 2
1 2 1
2 2
2 3
2 5
1 3 0
1 4 0
2 3
2 4
2 5
1 4 1
2 3
2 4
2 5

Example output:
5
4
4
3
1
4
5
1
5
4
1

Editorial:
We'll assume the arrays and the final permutation are 0-indexed from this point forward (you can shift values accordingly at the end).
Let's start with calculating the final array, without any updates. Let $$$c_i$$$ be the number of indices $$$j$$$ such that $$$p_j < p_i$$$ and $$$i < j$$$. It is easy to see that $$$c_i = i - b_i$$$. Now imagine sweeping from left to right, maintaining the array $$$a$$$. Let's say you're currently at index $$$i$$$, and you have a list of all indices $$$ \leq i$$$, where the location of some index $$$j$$$ is the value of $$$a_j$$$. You know that $$$i$$$ must be the $$$c_i$$$-th out of those (after inserting it into the list) as the $$$c_i$$$ smallest values must be before it. This means that you can insert index $$$i$$$ at the $$$c_i-th$$$ position in the list, and you need to find the final location of index $$$i$$$ in each query.
Now, let's support $$$O(1)$$$ updates and $$$O(n)$$$ queries. The first thing to note is that you don't need the entire array $$$a$$$ in each query, you just need to query some specific element. Assume you're querying the $$$i$$$-th element of the array. Let's repeat the algorithm mentioned above except instead of storing the lists, you only store the location of the $$$i$$$-th element for each query. Now, you keep some variable $$$loc$$$ which stores the location of the $$$i$$$-th element in the list. It is initialized to $$$c_i$$$, as it is first inserted to the $$$c_i$$$-th position. Now you sweep through all indices $$$j$$$ where $$$j > i$$$, and check if $$$loc$$$ is changed by the insert. This is only true if $$$loc \geq a[j]$$$. This allows for $$$O(1)$$$ updates but $$$O(n)$$$ queries, which is still too slow.
To speed this up, let's use sqrt-decomp. Divide the array into multiple blocks. For each block, let's store an array $$$next$$$ where $$$next_{loc}$$$ represents the final value of the variable $$$loc$$$ if it passes through the block. If we have this array, you can loop over all of the blocks and "jump" over them using the next array, querying in $$$O(n/B)$$$ time, where $$$B$$$ is the size of the block. But how do you calculate and update the $$$next$$$ array? Initially, you can calculate the next array in $$$O(n \cdot B)$$$, by going to each index and naively tracking its position. Updating it is harder. One observation to make is that for each index inside a block, there is some value such that if $$$loc \geq x$$$ it will be changed by the index, otherwise it will not. You can find all of those values for a single block using a binary indexed tree: sweep from left to right, query for the the smallest update $$$loc$$$ using a lower bound on the BIT, and increment a suffix. Then, you can increment all of those suffixes in the next array using another BIT, which would lead to $$$O(n \sqrt{n} + q \sqrt{n} \log{n})$$$, as queries are $$$O((n/B)\log{n})$$$ and updates are $$$O(B \log{n})$$$, which will probably be too slow.
To make this faster, note that the suffix that each element is responsible changes by at most one for all non-updated elements. This means that you can update the next array in $$$O(1)$$$ for these elements. However, the updated element's suffix might change by $$$O(n)$$$. To account for this, you can use another square root decomposition on the next array, which allows for $$$O(\sqrt{n})$$$ range updates, $$$O(1)$$$ point updates, and $$$O(1)$$$ point queries. This means that updates will remain $$$O(B \log{n})$$$, but queries will become $$$O(1)$$$, so the final complexity is $$$O(q \sqrt{n \log{n}})$$$ with the right blocksize, which is definitely fast enough (the model solution runs in $$$2$$$ seconds).
If you know of any faster solutions ($$$O(n\sqrt{n})$$$ or even $$$O(n \cdot \log^k{})$$$ let us know down in the comments).