Omkar and Time Travel
Contest: Technocup 2022 - Elimination Round 1
Difficulty rating: 3000
Tags: data structures, math

El Psy Kongroo.

Omkar is watching Steins;Gate.

In Steins;Gate, Okabe Rintarou needs to complete $$$n$$$ tasks ($$$1 \leq n \leq 2 \cdot 10^5$$$). Unfortunately, he doesn't know when he needs to complete the tasks.

Initially, the time is $$$0$$$. Time travel will now happen according to the following rules:

- For each $$$k = 1, 2, \ldots, n$$$, Okabe will realize at time $$$b_k$$$ that he was supposed to complete the $$$k$$$-th task at time $$$a_k$$$ ($$$a_k < b_k$$$).
- When he realizes this, if $$$k$$$-th task was already completed at time $$$a_k$$$, Okabe keeps the usual flow of time. Otherwise, he time travels to time $$$a_k$$$ then immediately completes the task.
- If Okabe time travels to time $$$a_k$$$, all tasks completed after this time will become incomplete again. That is, for every $$$j$$$, if $$$a_j>a_k$$$, the $$$j$$$-th task will become incomplete, if it was complete (if it was incomplete, nothing will change).
- Okabe has bad memory, so he can time travel to time $$$a_k$$$ only immediately after getting to time $$$b_k$$$ and learning that he was supposed to complete the $$$k$$$-th task at time $$$a_k$$$. That is, even if Okabe already had to perform $$$k$$$-th task before, he wouldn't remember it before stumbling on the info about this task at time $$$b_k$$$ again.

Please refer to the notes for an example of time travelling.

There is a certain set $$$s$$$ of tasks such that the first moment that all of the tasks in $$$s$$$ are simultaneously completed (regardless of whether any other tasks are currently completed), a funny scene will take place. Omkar loves this scene and wants to know how many times Okabe will time travel before this scene takes place. Find this number modulo $$$10^9 + 7$$$. It can be proven that eventually all $$$n$$$ tasks will be completed and so the answer always exists.

Input format:
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)  — the number of tasks that Okabe needs to complete.

$$$n$$$ lines follow. The $$$k$$$-th of these lines contain two integers $$$a_k$$$ and $$$b_k$$$ ($$$1 \leq a_k < b_k \leq 2n$$$)  — the time at which Okabe needs to complete the $$$k$$$-th task and the time that he realizes this respectively. All $$$2n$$$ of these times are distinct (so every time from $$$1$$$ to $$$2n$$$ inclusive appears exactly once in the input).

The next line contains a single integer $$$t$$$ ($$$1 \leq t \leq n$$$)  — the size of the set $$$s$$$ of tasks that lead to the funny scene.

The last line contains $$$t$$$ integers $$$s_1, s_2, \ldots, s_t$$$  — ($$$1 \leq s_k \leq n$$$, the numbers $$$s_1, s_2, \ldots, s_t$$$ are distinct)  — the set $$$s$$$ of tasks.

Output format:
Output a single integer  — the number of times that Okabe time travels until all tasks in the set $$$s$$$ are simultaneously completed, modulo $$$10^9 + 7$$$.

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

Note:
For the first sample, all tasks need to be completed in order for the funny scene to occur.

Initially, the time is $$$0$$$. Nothing happens until time $$$3$$$, when Okabe realizes that he should have done the $$$2$$$-nd task at time $$$2$$$. He then time travels to time $$$2$$$ and completes the task.

As the task is done now, he does not time travel again when the time is again $$$3$$$. However, at time $$$4$$$, he travels to time $$$1$$$ to complete the $$$1$$$-st task.

This undoes the $$$2$$$-nd task. This means that the $$$2$$$-nd task is not currently completed, meaning that the funny scene will not occur at this point even though the $$$1$$$-st task is currently completed and Okabe had previously completed the $$$2$$$-nd task.

Once it is again time $$$3$$$ he travels back to time $$$2$$$ once more and does the $$$2$$$-nd task again.

Now all tasks are complete, with Okabe having time travelled $$$3$$$ times.

The second sample has the same tasks for Okabe to complete. However, this time the funny scene only needs the first task to be completed in order to occur. From reading the above sample you can see that this occurs once Okabe has time travelled $$$2$$$ times.

Example input:
2
1 4
2 3
2
1 2

Example output:
3

Example input:
2
1 4
2 3
1
1

Example output:
2

Editorial:
Each time travel that Okabe performs creates a new set of completed tasks. We will take this as given, but it can be proven using ideas from the rest of the proof.
It thus suffices to count the number of distinct sets of task that come before the first one that contains $$$s$$$ as a subset. We should first figure out what kinds of sets will ever appear as a set of completed tasks at all; we will call these sets valid.
We will represent tasks below as intervals $$$[a_k, b_k]$$$.
First note that clearly not all sets are valid. If you have the intervals $$$[1, 2]$$$ and $$$[3, 4]$$$, clearly the set $$$\{[3, 4]\}$$$ is not a valid set. You can actually see that the same is true for the intervals $$$[1, 3]$$$ and $$$[2, 4]$$$ ($$$\{[2, 4]\}$$$ is not a valid set) by working through Okabe's activities.
This generalizes in a very important way: if there are two intervals $$$[a, b]$$$ and $$$[c, d]$$$ with $$$a < c$$$ and $$$b < d$$$, then any valid set that contains $$$[c, d]$$$ must also contain $$$[a, b]$$$. This is because if $$$d$$$ is reached to complete the task $$$[c, d]$$$, then $$$b$$$ will already have been reached to complete the task $$$[a, b]$$$ (since $$$b < d$$$), and any time travel that undoes $$$[a, b]$$$ must also undo $$$[c, d]$$$ (since $$$a < c$$$).
The above property is actually equivalent to being a valid set; we have already seen that it is necessary, and from the next part of the tutorial we will have way to prove that it is sufficient, but you should have some intuition for why this is true.
In order to solve the problem, we want to think about how to determine, given two valid sets, which one Okabe will encounter first. First, for any two valid sets, consider their last interval (i. e. interval with greatest value of $$$b$$$). If these are different, then the one with largest interval having greater $$$b$$$ will come later.
This is because for any valid set, the largest value of $$$b$$$ in any interval in that set is equal to the largest value of $$$b$$$ that Okabe has ever encountered. You can see this by noticing that the only way to undo a task is to perform a task with greater value of $$$b$$$; any task with smaller $$$b$$$ is either contained inside the first task, in which case it won't undo it, or also has a smaller value of $$$a$$$, in which case by the above property of valid sets it must already be completed.
Since the maximum value of $$$b$$$ that Okabe has ever encountered will only get larger as his activities continue, it follows that the valid set with larger maximum value of $$$b$$$ must occur later.
We can further see that for any two valid sets where the interval with largest $$$b$$$ is equal, we can discard that interval and consider the next largest interval from both valid sets.
This gives us an ordering of the valid sets. We can prove that the aformentioned property is sufficient for being a valid set by showing that at any valid set, the next valid set encountered is the immediately next one in the ordering. The details are left to the reader.
In order to use this to finally solve the problem, it is useful to represent valid sets in a different way. Specifically, we can represent a valid set $$$v$$$ as the set $$$u$$$ of intervals that aren't implied to be in $$$v$$$ by any other element of $$$v$$$. By thinking about the above property, you can see that $$$u$$$ is actually a set of recursively containing intervals; i. e. it contains an interval, then another interval inside that one, then another interval inside that one, etc.
We will consider the above representation to be ordered, so that the last interval is the one that contains all the others, and the first interval is the one inside of all the others.
We can now solve the problem. For the given set $$$s$$$, first determine its above representation; this can be done easily using sorting, discarding any redundant interval. The valid sets, also in their above representation, that come before $$$s$$$ are thus the ones that, excluding their common suffix with $$$s$$$, have a last interval whose $$$b$$$ is smaller than the $$$b$$$ for the last interval in $$$s$$$ excluding the common suffix.
We can therefore solve this as follows. We will count the number of above sets for each possible common suffix. For each suffix, let the last interval in $$$s$$$ not included in the suffix be $$$x$$$, and let the first interval in the suffix be $$$y$$$. The amount of sets for this suffix is equal to the amount of recursively containing sets that have a largest interval that is contained in $$$y$$$ whose value of $$$b$$$ is less than the value of $$$b$$$ for $$$x$$$.
We can compute this follows. We will maintain a range sum query data structure such as binary index tree. The data structure will have at each $$$a$$$, the number of recursively containing subsets whose largest interval is the one with that $$$a$$$ (once that interval has been processed). We will process the intervals in increasing order of $$$b$$$.
For each interval $$$x$$$, to put it into the data structure, we can simply perform a range query of literally the interval $$$x$$$, and add $$$1$$$ to the result. That will be equal to the number of recursively containing sets with $$$x$$$ as the largest interval, so we simply insert that into the data structure at the value of $$$a$$$ of $$$x$$$.
Before putting $$$x$$$ into the data structure, if it is in the representation of $$$s$$$, then we can find the answer for the suffix of $$$s$$$ that contains all intervals to the right of $$$x$$$ as follows. Since the intervals currently in the data structure are precisely the ones with value of $$$b$$$ less than $$$x$$$, the answer for that suffix is simply the range query of $$$y$$$ where $$$y$$$ is the immediately next interval after $$$x$$$ in $$$s$$$. We therefore perform this range query then add it to our answer.
Note that all of this computation doesn't count $$$s$$$ itself, but it does count the empty set which doesn't need to be counted, so our answer is correct.
The runtime of this solution is $$$O(n\lg n)$$$.