Freak Joker Process
Contest: COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 3100
Tags: binary search, data structures, sortings

After the success of the basketball teams formed and trained by Pak Chanek last year (Basketball Together), Pak Chanek wants to measure the performance of each player that is considered as a superstar.

There are $$$N$$$ superstar players that have been trained by Pak Chanek. At the end of the season, some calculations will be made on the performance of the $$$N$$$ players using an international method. Each player has two values $$$A_i$$$ and $$$B_i$$$ where each represents the offensive and defensive value of that player.

Define $$$\text{RankA}(i)$$$ as the offensive ranking of the $$$i$$$-th player, whose value is $$$c+1$$$ with $$$c$$$ here representing the number of $$$j$$$ ($$$1 \leq j \leq N$$$) such that $$$A_j>A_i$$$. Define $$$\text{RankB}(i)$$$ as the defensive ranking of the $$$i$$$-th player, whose value is $$$c+1$$$ with $$$c$$$ here representing the number of $$$j$$$ ($$$1 \leq j \leq N$$$) such that $$$B_j>B_i$$$.

Define $$$\text{RankOverall}(i)$$$ as the overall ranking of the $$$i$$$-th player, whose value is $$$c+1$$$ with $$$c$$$ here representing the number of $$$j$$$ ($$$1 \leq j \leq N$$$) such that $$$\text{RankA}(j)+\text{RankB}(j)<\text{RankA}(i)+\text{RankB}(i)$$$.

During the next $$$Q$$$ days, exactly one event will happen on each day. Each event is one of the three following possibilities:

- 1 k c – If $$$c$$$ is +, then $$$A_k$$$ increases by $$$1$$$. If $$$c$$$ is -, then $$$A_k$$$ decreases by $$$1$$$. ($$$1\leq k\leq N$$$; $$$c$$$ is + or -)
- 2 k c – If $$$c$$$ is +, then $$$B_k$$$ increases by $$$1$$$. If $$$c$$$ is -, then $$$B_k$$$ decreases by $$$1$$$. ($$$1\leq k\leq N$$$; $$$c$$$ is + or -)
- 3 k – Pak Chanek wants to know the value of $$$\text{RankOverall}(k)$$$ at that moment. ($$$1\leq k\leq N$$$)

Input format:
The first line contains a single integer $$$N$$$ ($$$1\leq N\leq10^5$$$) — the number of superstar players.

The second line contains $$$N$$$ integers $$$A_1, A_2, A_3 \ldots, A_N$$$ ($$$1 \leq A_i \leq 10^5$$$) — the offensive value of each player.

The third line contains $$$N$$$ integers $$$B_1, B_2, B_3 \ldots, B_N$$$ ($$$1 \leq B_i \leq 10^5$$$) — the defensive value of each player.

The fourth line contains a single integer $$$Q$$$ ($$$1\leq Q\leq10^5$$$) — the number of events.

The $$$j$$$-th of the next $$$Q$$$ lines contains the $$$j$$$-th event as described. At any moment, each value of $$$A_i$$$ and $$$B_i$$$ is always between $$$1$$$ and $$$10^5$$$ inclusive. There is at least one event of type $$$3$$$.

Output format:
For each event of type $$$3$$$, output a line containing an integer representing the value of $$$\text{RankOverall}(k)$$$ at that moment.

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

Note:
At the $$$8$$$-th event, $$$A=[3,2,1,3,2]$$$ and $$$B=[3,6,1,4,1]$$$. It can be obtained that the values of $$$\text{RankA}$$$ and $$$\text{RankB}$$$ for each player are as follows:

- $$$\text{RankA}(1)=1$$$, $$$\text{RankB}(1)=3$$$
- $$$\text{RankA}(2)=3$$$, $$$\text{RankB}(2)=1$$$
- $$$\text{RankA}(3)=5$$$, $$$\text{RankB}(3)=4$$$
- $$$\text{RankA}(4)=1$$$, $$$\text{RankB}(4)=2$$$
- $$$\text{RankA}(5)=3$$$, $$$\text{RankB}(5)=4$$$

So it can be obtained that $$$\text{RankOverall}(1)=2$$$.

Example input:
5
3 3 1 3 2
3 7 1 3 1
8
3 1
3 2
2 4 +
1 2 -
3 2
3 3
2 2 -
3 1

Example output:
2
1
2
5
2

Editorial:
We can solve this problem using square root decomposition. First we group the events into $$$\sqrt Q$$$ blocks of sizes $$$\sqrt Q$$$ and solve for each block independently.
For the start of each block, we can calculate all values of $$$A$$$ and $$$B$$$ easily. Additionally, we can calculate:
• $$$\text{biggerA}[x]$$$: the number of values of $$$A$$$ bigger than $$$x$$$.
• $$$\text{biggerB}[x]$$$: the number of values of $$$B$$$ bigger than $$$x$$$.
So, $$$\text{RankA}(i)=\text{biggerA}[A_i]+1$$$ and $$$\text{RankB}(i)=\text{biggerB}[B_i]+1$$$.
Notice that if we increase or decrease a value of $$$A$$$ by $$$1$$$, only one value of $$$\text{biggerA}$$$ changes. This means, the values of $$$\text{RankA}$$$ that change are only the changed $$$A$$$ value itself and a group of players with the same value of $$$A$$$. The same thing also applies for $$$B$$$, $$$\text{biggerB}$$$ and $$$\text{RankB}$$$.
For a single block, let's simulate the changes in $$$A$$$ and $$$B$$$ and keep track of which players change value at least once in the block. Additionally, keep track of which indices in $$$\text{biggerA}$$$ and $$$\text{biggerB}$$$ change at least once in the block and denote these indices as special values in each of $$$\text{biggerA}$$$ and $$$\text{biggerB}$$$.
For a single block, let's group the players into several types:
• A blue player is a player that changes value at least once in the block.
• An orange player is a non-blue player that has both of its $$$A$$$ and $$$B$$$ values as special values in each of $$$\text{biggerA}$$$ and $$$\text{biggerB}$$$.
• A yellow player is a non-blue player that has exactly one of its $$$A$$$ and $$$B$$$ values as a special value in $$$\text{biggerA}$$$ or $$$\text{biggerB}$$$ respectively.
• The rest are white players.
Notice that there are at most $$$\sqrt Q$$$ blue players and at most $$$\sqrt Q$$$ special values in each of $$$\text{biggerA}$$$ and $$$\text{biggerB}$$$.
Before simulating the events in the block, we must do some precomputations.
For orange and white players only, calculate the following:
• $$$\text{smallerOverall}[x]$$$: the number of orange and white players with $$$\text{RankA}+\text{RankB}<x$$$.
In order to maintain the value above, for orange players, calculate the following:
• $$$\text{cnt}[i][j]$$$: the number of orange players whose values of $$$A$$$ and $$$B$$$ are the $$$i$$$-th and $$$j$$$-th special values in $$$\text{biggerA}$$$ and $$$\text{biggerB}$$$ respectively.
For each special value in $$$\text{biggerA}$$$, consider every yellow player that has that value of $$$A$$$. Notice that their values of $$$\text{RankB}$$$ will not change in the block. So we can precompute their values of $$$\text{RankB}$$$ and maintain them in a sorted array. We do a similar thing for the special values in $$$\text{biggerB}$$$ and their yellow players.
After doing all those precomputations, we simulate each event in the block. We do each change while maintaining all values of $$$A$$$, $$$B$$$, $$$\text{biggerA}$$$, $$$\text{biggerB}$$$, and $$$\text{smallerOverall}$$$. To maintain $$$\text{smallerOverall}$$$ while considering orange players, notice that we can update it naively using the values of $$$\text{cnt}$$$ since there are at most $$$\sqrt Q$$$ different values of $$$\text{RankA}+\text{RankB}$$$ of orange players that change in each change event (because there are at most $$$\sqrt Q$$$ special values) and each change in $$$\text{RankA}+\text{RankB}$$$ only changes one value of $$$\text{smallerOverall}$$$.
For each query event asking $$$\text{RankOverall}(k)$$$, do the following:
• Calculate $$$w=\text{RankA}(k)+\text{RankB}(k)$$$.
• For each blue player, calculate its $$$\text{RankA}+\text{RankB}$$$ and check if its value is smaller than $$$w$$$.
• For the orange and white players, just use the value of $$$\text{smallerOverall}(w)$$$.
• For the yellow players, for each special value, use binary search to find the number of players with $$$\text{RankA}+\text{RankB}<w$$$ (use $$$\text{RankB}<w-\text{RankA}$$$ for the special values in $$$\text{biggerA}$$$).
• The value of $$$\text{RankOverall}(k)$$$ can be calculated using all values above.
Notice that there is a log factor for sorting and binary search.
Time complexity: $$$O((N+Q)\sqrt{Q}\log N)$$$
Note: There is a $$$O((N+Q)\sqrt{Q})$$$ solution but the implementation sounds very heavy and tedious so it is not necessary to get accepted.