A Certain Magical Party
Contest: Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
Difficulty rating: 3300
Tags: combinatorics, data structures, greedy, sortings

There are $$$n$$$ people at a party. The $$$i$$$-th person has an amount of happiness $$$a_i$$$.

Every person has a certain kind of personality which can be represented as a binary integer $$$b$$$. If $$$b = 0$$$, it means the happiness of the person will increase if he tells the story to someone strictly less happy than them. If $$$b = 1$$$, it means the happiness of the person will increase if he tells the story to someone strictly more happy than them.

Let us define a speaking order as an ordering of the people from left to right. Now the following process occurs. We go from left to right. The current person tells the story to all people other than himself. Note that all happiness values stay constant while this happens. After the person is done, he counts the number of people who currently have strictly less/more happiness than him as per his kind of personality, and his happiness increases by that value. Note that only the current person's happiness value increases.

As the organizer of the party, you don't want anyone to leave sad. Therefore, you want to count the number of speaking orders such that at the end of the process all $$$n$$$ people have equal happiness.

Two speaking orders are considered different if there exists at least one person who does not have the same position in the two speaking orders.

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

The second line contains a sequence of $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1 \leq a_i \leq 2n$$$)  — the happiness values.

The third line contains a sequence of $$$n$$$ binary numbers $$$b_1,b_2,...,b_n$$$ ($$$b_i \in \{0,1\}$$$)  — the kinds of personality.

Output format:
Output the number of different valid speaking orders. Since this number can be large, output it modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Here is the explanation for the first example. One valid speaking order is $$$[2,1,4,3]$$$ (here, we have written the indices of each person). Each step shows the current happiness values and results.

Step $$$1$$$: $$$[1,2,4,4]$$$ $$$\rightarrow$$$ Person $$$2$$$ tells the story to others. Since his kind of personality is $$$1$$$, his happiness increases by $$$2$$$ since persons $$$3$$$ and $$$4$$$ have strictly greater happiness.

Step $$$2$$$: $$$[1,4,4,4]$$$ $$$\rightarrow$$$ Person $$$1$$$ tells the story to others. Since his kind of personality is $$$1$$$, his happiness increases by $$$3$$$ since persons $$$2$$$, $$$3$$$ and $$$4$$$ have strictly greater happiness.

Step $$$3$$$: $$$[4,4,4,4]$$$ $$$\rightarrow$$$ Person $$$4$$$ tells the story to others. Since his kind of personality is $$$0$$$, his happiness increases by $$$0$$$ since no one has strictly lesser happiness.

Step $$$4$$$: $$$[4,4,4,4]$$$ $$$\rightarrow$$$ Person $$$3$$$ tells the story to others. Since his kind of personality is $$$0$$$, his happiness increases by $$$0$$$ since no one has strictly lesser happiness.

At the end, everyone has equal happiness.

Note that $$$[2,1,3,4]$$$ is also a valid answer for this example.

It can be shown that there is no valid ordering for the second example.

Example input:
4
1 2 4 4
1 1 0 0

Example output:
2

Example input:
4
3 4 3 1
0 1 0 0

Example output:
0

Editorial:
First of all, if there is only $$$1$$$ distinct value of happiness, any ordering is fine since no one has strictly greater or lesser happiness, and the answer is $$$n!$$$. From here on, we assume that there are at least $$$2$$$ distinct values of happiness.
Note: The notation $$$<u,v>$$$ refers to elements with happiness $$$u$$$ and behaviour $$$v$$$.
Observation 1: The happiness of a person can never decrease. It is obvious.
Let's call the final happiness value all elements will be equal to as the target value $$$T$$$. Also, let the smallest happiness value of the array be $$$m$$$, and the largest be $$$M$$$. Note that $$$T \geq M$$$, otherwise, it is impossible for a valid order to exist, from observation $$$1$$$.
Observation 2: For all $$$x<T$$$, there can be at most one occurrence of $$$<x,1>$$$ in the array.
Proof:
Let's say there is more than one occurrence of $$$<x,1>$$$. Let's say at some point, we can place one occurrence of it in our order, and we place it. But then for the remaining occurrences, it immediately becomes impossible to place them anymore, because the number of strictly greater values increases by $$$1$$$, and can only increase from there. Hence, contradiction.
—————
Observation 3: There is only one possible $$$T$$$, given by $$$m+n-1$$$.
Proof:
Let's say we have $$$<m,0>$$$. Then no matter what we do, its final happiness value will still be $$$m$$$, since there will never be a value strictly lesser than it. This means $$$T=m$$$. This however, breaks our assumption of $$$2$$$ distinct values. So only $$$<m,1>$$$ can exist. But if that exists, from observation $$$2$$$, exactly one such occurrence exists. The number of values strictly greater than $$$m$$$ will always be constant. So, no matter when we place it, the final happiness value is going to be $$$m+n-1$$$.
—————
Observation 4: If it is possible to place multiple numbers in the order at a certain point ( i.e. if there are multiple possible $$$<u,v>$$$ place which will all yield $$$<T,v>$$$ ), it is always better to prefer the larger number, and to place a number with behaviour $$$1$$$ over one with behaviour $$$0$$$ in case of a tie.
Proof: Let's say you pick something smaller than the larger number. Now this number becomes $$$T$$$, which is $$$\geq M$$$. Now consider the larger number. If it had a $$$0$$$, now it is impossible to place it anymore, because the number of numbers strictly lesser has reduced by $$$1$$$, and it can only reduce. A similar argument follows for $$$1$$$.
In the same group, you have to prefer $$$1$$$s over $$$0$$$s. Let's say you placed the $$$0$$$ first. Now the number of numbers strictly greater has increased by $$$1$$$, and can only increase. Therefore you can never place the $$$1$$$ now. Placing the $$$1$$$ first does not affect the viability of placing the $$$0$$$s.
Important: If $$$T=M$$$, the $$$<M,1>$$$ group is special, since it doesn't matter when you place it since the final happiness value will still be $$$M$$$, and it won't affect any other group's viability either. But the observation still holds.
In fact, except the $$$<M,1>$$$ group in the case of $$$T=M$$$, you have to follow this order. This means the order is unique upto considering equal elements as indistinguishable. This means, we can only choose the order of placing equal values. We cannot choose the occupied positions in the final order.
Hence the count is going to be the product of the number of possible permutations for each group.
$$$$$$\begin{aligned}P=\prod_{\text{all }<u,v>} {cnt_{<u,v>}!}\end{aligned}$$$$$$
—————
Observation 5: For a valid ordering (if exists), the $$$0$$$ behaving people would be sorted in non-decreasing order of initial happiness.
Proof: We assume the contrary: Suppose for $$$x > y$$$, $$$<x, 0>$$$ speaks before $$$<y, 0>$$$ in some valid order. Since it is known that both finally become $$$<T, 0>$$$, it must be the case that there were $$$(T - x)$$$ people with a smaller happiness than $$$x$$$, when $$$x$$$ speaks and $$$(T - y)$$$ people with a smaller happiness than $$$y$$$, when $$$y$$$ speaks. As $$$x > y$$$, everyone having a happiness less than $$$y$$$ must also have a happiness less than $$$x$$$. Therefore when $$$y$$$ speaks at least $$$(T - y)$$$ people had a happiness smaller than $$$x$$$. Now $$$(T - x) < (T - y)$$$; which means the number of people having a value less than $$$x$$$ increased. But the happiness of each person can only increase, and hence the number of poeple with a happiness less than $$$x$$$ cannot increase; contradiction.
—————
Observation 6: For a valid ordering (if exists) and at any intermediate step, for all $$$1$$$ behaving people $$$<u, 1>$$$ yet to speak, the number of people with a larger happiness than $$$u$$$ cannot exceed $$$(T - u)$$$. In other words, if we placed $$$<u, 1>$$$ at any intermediate step, its final happiness would not exceed $$$T$$$.
Proof: The happiness of everyone can only increase. So if the number of people with happiness greater than $$$<u, 1>$$$ exceeds $$$(T - u)$$$ before $$$<u, 1>$$$ has spoken, the number of people with a happiness greater than $$$u$$$ would not decrease when $$$u$$$ subsequently speaks. This means the final happiness of this person would be greater than $$$T$$$, which cannot happen.
—————
As mentioned before, in the case of the group $$$<M,1>$$$ if $$$T=M$$$, it doesn't matter where we place them in the order, but the order of the remaining elements is fixed. If there are $$$S$$$ occurrences of this group, then we have $$$n$$$ spots we can choose to place these values of the group in, and then the rest of the elements will follow the order in the remaining positions. The count $$$P$$$ is going to be multiplied by $$$\binom{n}{S}$$$.
However, it may be the case that no such ordering exists. We thus try to find an order using Observation 4 and speed it up using Observation 5 and Observation 6.
We notice that we can have a brute force simulation of Observation 4 to find the order in $$$\mathcal{O}(n^2)$$$ time. However, we can do the following:
1. Place all occurrences of $$$<T, 1>$$$ at the beginning as their positions don't matter.
2. Keep a sorted (non-decreasing) list of all the $$$0$$$ behaving people who are yet to speak. From Observation 5 the only candidate who can be placed from this list at a given step is the least happy candidate.
3. Keep a sorted (increasing) list of all $$$1$$$ behaving people who are yet to speak where we keep track of the maximum of the final happiness reached if they were to speak now (i.e. their initial happiness + the number of people with a strictly greater happiness at present) among all people in this list. From Observation 6, we know that if this maximum exceeds $$$T$$$, there is no possible ordering and we output $$$0$$$. Hence from now we will assume that the maximum happiness reached if they were to talk now to be at most $$$T$$$.
4. At each step, there are only two potential speakers that we need to check (since we are breaking ties using Observation 4): The least happy $$$0$$$ behaving person (if its happiness reached currently is $$$T$$$) and the maximum stored in the last step (if it is equal to $$$T$$$). If neither is valid, we report no answer.
5. Otherwise, we break ties using Observation 4 and make that person speak. We change their happiness to $$$T$$$ and the final happiness values if they speak now, of all the $$$1$$$ behaving people that had a greater happiness (handled in step $$$3$$$) than the current person would increase by $$$1$$$.
6. If we can complete the entire process, we have a valid ordering.
This can be done quickly using two segment trees: One for keeping the happiness reached values of $$$1$$$ behaving people yet to speak and storing their maximum (so that steps $$$3$$$ and $$$5$$$ become max query and range updates); and another for keeping the count of people having a particular happiness value (to speed up finding the current happiness value if they speak now for the least happy $$$0$$$ behaving person in step $$$4$$$).
Time complexity: $$$\mathcal{O}(n\log n)$$$