Fancy Fence
Contest: Central-European Olympiad in Informatics, CEOI 2020, Day 1 (IOI, Unofficial Mirror Contest, Unrated)
Difficulty rating: 1800
Tags: *special, data structures, dsu, implementation, math, sortings

Everybody knows that Balázs has the fanciest fence in the whole town. It's built up from $$$N$$$ fancy sections. The sections are rectangles standing closely next to each other on the ground. The $$$i$$$th section has integer height $$$h_i$$$ and integer width $$$w_i$$$.  We are looking for fancy rectangles on this fancy fence.  A rectangle is fancy if:

- its sides are either horizontal or vertical and have integer lengths
- the distance between the rectangle and the ground is integer
- the distance between the rectangle and the left side of the first section is integer
- it's lying completely on sections

Input format:
The first line contains $$$N$$$ ($$$1\leq N \leq 10^{5}$$$) – the number of sections.  The second line contains $$$N$$$ space-separated integers, the $$$i$$$th number is $$$h_i$$$ ($$$1 \leq h_i \leq 10^{9}$$$).  The third line contains $$$N$$$ space-separated integers, the $$$i$$$th number is $$$w_i$$$ ($$$1 \leq w_i \leq 10^{9}$$$).

Output format:
You should print a single integer, the number of fancy rectangles modulo $$$10^9+7$$$. So the output range is $$$0,1,2,\ldots, 10^9+6$$$.

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

Note:
Scoring:
$$$ \begin{array}{|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & 0 & \text{sample}\\ \hline 2 & 12 & N \leq 50 \: \text{and} \: h_i \leq 50 \: \text{and} \: w_i = 1 \: \text{for all} \: i \\ \hline 3 & 13 & h_i = 1 \: \text{or} \: h_i = 2 \: \text{for all} \: i \\ \hline 4 & 15 & \text{all} \: h_i \: \text{are equal} \\ \hline 5 & 15 & h_i \leq h_{i+1} \: \text{for all} \: i \leq N-1 \\ \hline 6 & 18 & N \leq 1000\\ \hline 7 & 27 & \text{no additional constraints}\\ \hline \end{array} $$$

The fence looks like this:

There are 5 fancy rectangles of shape:

There are 3 fancy rectangles of shape:

There is 1 fancy rectangle of shape:

There are 2 fancy rectangles of shape:

There is 1 fancy rectangle of shape:

Example input:
2
1 2
1 2

Example output:
12

Editorial:
Subtask 2
$$$N, h_i \leq 50, w_i = 1$$$
There are at most $$$50^4$$$ different rectangles.  For all of them, we can check if they are fancy or not. This can be done in constant time with some precomputation.
Subtask 3
$$$h_i = 1$$$ or $$$h_i = 2$$$ for all $$$i$$$.
Consider a rectangle with height $$$1$$$ and width $$$K$$$.  Lemma: There are $$$\binom{K+1}{2}$$$ fancy rectangles in it.   Proof: There are $$$K-p+1$$$ fancy rectangles with width $$$p$$$: $$$$$$\sum_{p=1}^{K} (K-p+1) = \binom{K+1}{2}$$$$$$
Now we can solve subtask 3: There are 2 types of fancy rectangles, the ones with height $$$1$$$, and the ones with height $$$2$$$.
We can easily calculate the answer, applying the previous lemma in $$$O(N)$$$ time.
A helpful observation
Consider a rectangle with height $$$A$$$ and width $$$B$$$.  Let's denote the number of fancy rectangles contained within this big rectangle by $$$T_{A,B}$$$. Now we have  $$$$$$T_{A,B} = \binom{A+1}{2} \cdot \binom{B+1}{2}$$$$$$ Proof:  We can chose $$$\binom{A+1}{2}$$$ different horizontal lines to form the horizontal side of a fancy rectangle. The same holds for the vertical side.
Note that $$$\binom{X}{2} = \dfrac{X(X-1)}{2}$$$, where $$$X(X-1)$$$ is always divisible by 2.
Subtask 4
The solution follows easily from the previous lemma.
This subtask can be solved in $$$O(N)$$$ time.
Subtask 5
The heights are in increasing order.
Let $$$W_i$$$ be the sum of section widths from the $$$i$$$th to the $$$N$$$th section.  The answer is given by the formula: $$$$$$\sum_{i=1}^{N} T_{h_i,W_i} - T_{h_{i-1},W_i},$$$$$$ where $$$h_0 = 0$$$.
This way, the subtask can be solved in $$$O(N)$$$ time.
Subtask 6
$$$N \leq 1000$$$
For all $$$1 \leq i \leq j \leq N$$$, we calculate the number of fancy rectangles whose left side is part of the $$$i$$$th section and right side is part of the $$$j$$$th section.  Let $$$H$$$ be the minimum of section heights from the $$$i$$$th to the $$$j$$$th section.  Let $$$W$$$ be the sum of section widths from the $$$i$$$th to the $$$j$$$th section.  The number of fancy rectangles is (if $$$i \ne j$$$): $$$$$$T_{H,W} - T_{H,W-w_i} - T_{H,W-w_j} + T_{H,W-w_i-w_j},$$$$$$ which can be precomputed for all $$$H$$$.
This subtask can be solved in $$$O(N^2)$$$.
Subtask 7
Original constraints.
Sorting
Let's sort the sections in decreasing order according to their heights.
Let us denote the original index of the $$$i$$$ section by $$$p_i$$$. In the $$$i$$$th step, we calculate the number of fancy rectangles lying exclusively on the first $$$i$$$ sections.
Let $$$x$$$ be the smallest index for which the $$$x$$$th, $$$x+1$$$th ... $$$p_i-1$$$th sections preceed the $$$p_i$$$th section.  Let $$$y$$$ be the biggest index for which the $$$p_i+1$$$th, $$$p_i+2$$$th ... $$$y$$$th sections succeed the $$$p_i$$$th section.  Write $$$$$$X_i = \sum_{j=x}^{p_i-1} w_j, \qquad Y_i = \sum_{j=p_i+1}^{y} w_j.$$$$$$ In the $$$i$$$th step, the answer increases by $$$T_{h_{p_i}, X_i+Y_i+w_{p_i}}-T_{h_{p_i},X_i}-T_{h_{p_i},Y_i}$$$. To calculate values $$$X_i$$$ and $$$Y_i$$$ efficiently, we have to combine consecutive intervals (e.g. using DSU or similar, more simple methods). At the start, there are $$$N$$$ intervals, each one consists of exactly one section. In the $$$i$$$th step, we shall combine the sections from the $$$x$$$th to the $$$y$$$th. For all intervals, the sum of widths of sections contained by the interval has to be stored as well.
This subtask can be solved in $$$O(NlogN)$$$ time.
Linear
Let's iterate through the sectionss from left to right maintaining a stack of sections with the following property: from bottom to top the height of sections are increasing and after the $$$i$$$th section is processed every fancy rectangle not present in the stack is already counted.
When at the $$$i$$$th section three cases are possible, let the top of the stack contain a section with dimensions $$$H\times W$$$:
• if $$$h_i=H$$$ we can easily modify $$$W$$$ and increase it by $$$w_i$$$ not hurting the invariant described above
• if $$$h_i>H$$$ we can just push a $$$h_i \times w_i$$$ rectangle to the top of the stack
• if $$$h_i<H$$$ then we have to pop some elements from the stack until $$$h_i$$$ will be greater or equal to the height of the section on the top of the stack. While doing the popping we accumulate the width of the new top element (i.e. the sum of widths of all elements popped plus $$$w_i$$$) and also with a similar strategy to subtask 5 the number of fancy rectangles that will not be present in the stack should be calculated.
Overall the time complexity of this solution is $$$O(N)$$$ since every rectangle is pushed and popped exactly once while doing a constant amount of operations.