Problem: perimetric_ch3 (2020 round1)

**Note: This problem shares similarities with Chapters [1](https://www.facebook.com/codingcompetitions/hacker-cup/2020/round-1/problems/A1) and [2](https://www.facebook.com/codingcompetitions/hacker-cup/2020/round-1/problems/A2). The solution to any chapter may help with solving the others, so please consider reading all of them.**

After a highly successful haul from the log drive, Connie the contractor is tasked with building a number of houses in the Great White North. For each job, the client has provided a floor plan consisting of \(N\) rectangular rooms, numbered from 1 to \(N\). From a bird's-eye view, the rooms are arranged on a 2-dimensional plane, with axis-aligned walls. The southern wall of each room has y-coordinate 0.

The \(i\)th rectangular room has southwest corner \((L_i, 0)\) and northeast corner \((L_i + W_i, H_i\)). **In this chapter of the problem, the rooms have non-decreasing \(H\) values \((H_1 \le H_2 \le ... \le H_N)\).** Since houses often have shared regions (such as a common living/dining area), these rooms may overlap with one another.

Unfortunately, [log houses are quite susceptible to air leakage](https://www.energy.gov/energysaver/types-homes/energy-efficiency-log-homes). Connie knows that she must install additional insulation to keep the houses warm and energy-efficient during the harsh Canadian winters. In order to determine the amount of insulation material required, Connie will first need to gather some metrics: the perimeters around various combinations of rooms.

Specifically, let \(P_i\) be the perimeter of the union of rooms \(1..i\). Note that any given point is considered to be within the union if and only if it's within at least one of the rooms' rectangles (including right on an edge), and that the union might not form a single connected polygon. Please help compute the product \((P_1 * P_2 * ... * P_N)\). As this product may be very large, you should compute its value modulo 1,000,000,007.

In order to reduce the size of the input, the rooms' coordinates will not all be provided explicitly. Instead, you'll be given the first \(K\) values \(L_{1..K}\), \(W_{1..K}\), and \(H_{1..K}\), as well as the three quadruples of constants \((A_L, B_L, C_L, D_L)\), \((A_W, B_W, C_W, D_W)\), and \((A_H, B_H, C_H, D_H)\), and must then compute \(L_{(K+1)..N}\), \(W_{(K+1)..N}\), and \(H_{(K+1)..N}\) as follows:

\(L_i = ((A_L * L_{i-2} + B_L * L_{i-1} + C_L) \text{ modulo } D_L) + 1\) for \(i > K\)
\(W_i = ((A_W * W_{i-2} + B_W * W_{i-1} + C_W) \text{ modulo } D_W) + 1\) for \(i > K\)
\(H_i = ((A_H * H_{i-2} + B_H * H_{i-1} + C_H) \text{ modulo } D_H) + 1\) for \(i > K\)

# Input

Input begins with an integer \(T\), the number of floor plans. For each plan, there are 7 lines. 

The first line contains the 2 space-separated integers \(N\) and \(K\).

The second line contains the \(K\) space-separated integers \(L_{1..K}\).

The third line contains the 4 space-separated integers \(A_L\), \(B_L\), \(C_L\), and \(D_L\).

The fourth line contains the \(K\) space-separated integers \(W_{1..K}\).

The fifth line contains the 4 space-separated integers \(A_W\), \(B_W\), \(C_W\), and \(D_W\).

The sixth line contains the \(K\) space-separated integers \(H_{1..K}\).

The seventh line contains the 4 space-separated integers \(A_H\), \(B_H\), \(C_H\), and \(D_H\).

# Output

For the \(i\)th floor plan, print a line containing *"Case #i: "* followed by a single integer, the product \((P_1 * P_2 * ... * P_N)\) as defined above, modulo 1,000,000,007.

# Constraints

\(1 \le T \le 90\) 
\(2 \le N \le 1,000,000\)
\(2 \le K \le N\)
\(0 \le A_L, B_L, C_L, A_W, B_W, C_W, A_H, B_H, C_H \le 1,000,000,000\)
\(1 \le D_L, D_W, D_H \le 500,000,000\)
\(1 \le L_i \le D_L\)
\(1 \le W_i \le D_W\)
\(1 \le H_i \le D_H\)
\(H_1 \le H_2 \le ... \le H_N\)

The sum of \(N\) across all floor plans is at most 10,000,000.

# Explanation of Sample

For the first floor plan, \(L = [1, 2]\) and \(H = [3, 3]\). The union of just the first room's rectangle is equivalent to that rectangle, which has a width of 2 and a height of 3, and therefore a perimeter of 10. The union of both rooms' rectangles is equivalent to a single rectangle with a width of 3 and a height of 3 (with southwest corner (1, 0)), having a perimeter of 12. The answer is therefore \((10 * 12)\text{ modulo }1\text{,}000\text{,}000\text{,}007 = 120\).

For the second floor plan, \(P = [10, 20]\).

For the third floor plan, \(P = [8, 18, 36, 52, 54]\).

For the fourth floor plan: 
\(L = [14, 5, 14, 27, 13, 14, 12, 2, 18, 43]\) 
\(W = [6, 4, 13, 32, 8, 7, 22, 32, 26, 28]\) 
\(H = [11, 13, 14, 16, 17, 19, 20, 22, 23, 25]\)
\(P = [34, 68, 88, 156, 164, 168, 168, 158, 160, 188]\)


Sample input:
5
2 2
1 2
0 0 0 100
2 2
0 0 0 100
3 3
0 0 0 100
2 2
10 20
0 0 0 100
2 2
0 0 0 100
3 3
0 0 0 100
5 5
8 3 10 16 2
0 0 0 100
3 1 5 2 18
0 0 0 100
1 4 6 6 9
0 0 0 100
10 3
14 5 14
4 7 2 47
6 4 13
2 3 17 33
11 13 14
1 0 2 31
50 10
100 26 4 28 106 59 9 105 10 97
14 40 784 4832
130 12 82 487 12 30 214 104 104 527
21 81 410 605
38 103 109 109 116 157 181 217 234 234
1 0 16 951


Sample output:
Case #1: 120
Case #2: 200
Case #3: 14556672
Case #4: 842325442
Case #5: 848278949


Solution: As in Chapters 1 and 2 of this problem, we'll process the rectangles one by one while computing \(P_{1..N}\). When processing the \(i\)th rectangle, we can't afford to compute the perimeter of the union of the first \(i\) rectangles from scratch (as this would result in an inefficient algorithm with time complexity at least \(O(N^2)\)), so we'll instead compute how the inclusion of this rectangle affects the existing rectangle union (and therefore how \(P_i\) differs from \(P_{i-1}\), assuming that \(P_0 = 0\)).

Unlike in Chapter 2, the heights of the existing rectangles do matter in this chapter. A convenient way to maintain information about them is with an ordered set of vertical line segments (or "height changes") present in the union's perimeter. Each of these is a tuple \((x, y_1, y_2)\) indicating that, at x-coordinate \(x\), the top portion of the perimeter moves up/down from y-coordinate \(y_1\) to y-coordinate \(y_2\) when tracing the perimeter from left to right.

When processing the \(i\)th rectangle, we can begin by tentatively adding on its full perimeter (\(2(W_i + H_i)\)) to the union's current perimeter, and then separately consider the amount of horizontal and vertical perimeter we've overcounted. Similarly to Chapter 2, the total horizontal perimeter of the rectangle union is equal to twice the total length of x-coordinates spanned by at least one rectangle, meaning that the amount of overcounted horizontal perimeter is twice the total length of x-coordinates spanned by at least one existing rectangle within the interval \([L_i, L_i + W_i]\). We can tally that up by iterating over the height changes which the \(i\)th rectangle overlaps with, noting that the interval from a height change \((x, y_1, y_2)\) to the next height change is spanned by an existing rectangle if and only if \(y_2 > 0\). As for overcounted vertical perimeter, each existing height change which the \(i\)th rectangle overlaps (inclusively) with is entirely swallowed up and should no longer contribute its vertical length to the union's perimeter. Furthermore, the height of the existing perimeter at x-coordinate \(L_i\) (computable by looking at the nearest height change before or after that x-coordinate) should be subtracted (as the perimeter actually only goes down from the top of the \(i\)th rectangle to that y-coordinate rather than all the way to \(0\)), and the same applies for x-coordinate \(L_i + W_i\).

Based on the above observations, as long as we're able to update the ordered set of height changes for each new rectangle (by iterating over ones that it overlaps with, deleting them, and then inserting new ones at its left and right ends if appropriate), we can also easily update the union's current perimeter along the way. As in Chapter 2, we'll use an ordered set implementation capable of supporting the necessary searching, deletion, and insertion operations in logarithmic time (using a BBST). Given that our ordered set will contain at most \(2N\) elements (two height changes per rectangle) and that each rectangle's height changes will be inserted/deleted at most once, this approach yields a time complexity of \(O(N log(N))\).


Code: // Perimetric - Chapter 3
// Solution by Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x < 0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x * x); }
string plural(string s) { return(Sz(s) && s[Sz(s) - 1] == 'x' ? s + "en" : s + "s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#define GETCHAR getchar_unlocked

bool Read(int& x)
{
  char c, r = 0, n = 0;
  x = 0;
  for (;;)
  {
    c = GETCHAR();
    if ((c < 0) && (!r))
      return(0);
    if ((c == '-') && (!r))
      n = 1;
    else
      if ((c >= '0') && (c <= '9'))
        x = x * 10 + c - '0', r = 1;
      else
        if (r)
          break;
  }
  if (n)
    x = -x;
  return(1);
}

#define LIM 1000001
#define MOD 1000000007

#define TR pair<int, PR>

LL cur, ans;
int L[LIM], W[LIM], H[LIM];
set<TR> S;

void ReadSeq(int* V, int N, int K)
{
  int i, A, B, C, D;
  Fox(i, K)
    Read(V[i]);
  Read(A), Read(B), Read(C), Read(D);
  FoxI(i, K, N - 1)
    V[i] = ((LL)A * V[i - 2] + (LL)B * V[i - 1] + C) % D + 1;
}

void ProcessRect(int L, int R, int H)
{
  // tentatively add full rectangle perimeter
  cur += 2 * (R - L + H);
  // iterate over union height changes overlapping with this rectangle
  auto I = prev(S.lower_bound(mp(L, mp(-1, -1))));
  auto J = S.lower_bound(mp(R + 1, mp(-1, -1)));
  TR A = *I, B = *J;
  while (I->x < B.x)
  {
    J = I, I++;
    if (J->y.y)
      cur -= 2 * (min(R, I->x) - max(L, J->x)); // subtract swallowed-up horizontal perimeter
    if (J->x >= L)
    {
      cur -= Abs(J->y.x - J->y.y); // subtract swallowed-up vertical perimeter
      S.erase(J);
    }
  }
  cur -= A.y.y + B.y.x; // subtract swallowed-up vertical perimeter at either end of this rectangle
  // insert new union height changes at either end of this rectangle
  if (A.y.y != H)
    S.insert(mp(L, mp(A.y.y, H)));
  if (B.y.x != H)
    S.insert(mp(R, mp(H, B.y.x)));
}

int ProcessCase()
{
  int N, K, i;
  // input
  Read(N), Read(K);
  ReadSeq(L, N, K);
  ReadSeq(W, N, K);
  ReadSeq(H, N, K);
  // process rectangles, while maintaining set of union height changes
  cur = 0, ans = 1;
  S.clear();
  S.insert(mp(-1, mp(0, 0)));
  S.insert(mp(INF + 1, mp(0, 0)));
  Fox(i, N)
  {
    ProcessRect(L[i], L[i] + W[i], H[i]);
    ans = (LL)ans * (cur % MOD) % MOD;
  }
  return(ans);
}

int main()
{
  int T, t;
  Read(T);
  Fox1(t, T)
    printf("Case #%d: %d\n", t, ProcessCase());
  return(0);
}