Problem: spider_spring (2020 finals)

A family of water spiders lives at a spring located on an earthquake hotspot. The spring features \(N\) columns of rocks in a row, numbered \(1\) to \(N\) from left to right. Each rocky column \(i\) has a width of 1 cm and a height of \(H_i\) cm.

The spring always has some global water level. The rocky columns can each be below the water, at water level, or protrude above its surface. A spider in a given column must float on the surface of the water (if the rock is below water level) or stand atop the rock (if it's at or above water level). This means that, when the water level is W cm, the **effective elevation** at column \(i\) is \(max(H_i, W)\) cm.

For example, the following diagram illustrates a spring with \(H = [2, 1, 3, 1]\) and \(W = 2\), with the effective elevations outlined in black:

{{PHOTO_ID:1583104035206937}}

Water spiders sometimes want to travel from one column \(a\) to another column \(b\). This involves starting horizontally in the middle of column \(a\), at its effective elevation, and walking along the outline of the effective elevations until ending up horizontally in the middle of column \(b\). This may include walking left/right across the tops of rocks or the surface of the water, as well as up/down along the sides of the protruding rocks. Note that a spider's route will never take it left of column \(1\), right of column \(N\), below the surface of the water, nor into mid-air.

For example, the path which a water spider would follow from column 1 to column 4 (having a length of 5 cm) is indicated in red below:

{{PHOTO_ID:862340924576901}}

Unfortunately for the spring's inhabitants, frequent earthquakes occur, altering the heights of the rocky columns and the water. The spiders would like to survey the accessibility of the spring after each earthquake.

Specifically, \(M\) earthquakes are about to occur, one after another. As part of the \(i\)th earthquake, the height of each rocky column \(c\) such that \(X_i \le c \le min(X_i + Y_i - 1, N)\) will become equal to \(Z_i\) cm, and the global water level will become \(W_i\) cm. After each earthquake \(i\), the spiders are interested in the current sum of travel distances (in cm) over all \(N*(N - 1)\) ordered pairs of starting and ending columns — we'll call this quantity \(S_i\).

Please determine the value of \((S_1 * S_2 * ... * S_M)\) modulo 1,000,000,007.

In order to reduce the size of the input, the above values will not all be provided explicitly. Instead, you'll be given the first \(K\) values \(H_{1..K}\), \(X_{1..K}\), \(Y_{1..K}\), \(Z_{1..K}\), and \(W_{1..K}\), as well as the five quadruples of constants \((A_H, B_H, C_H, D_H)\), \((A_X, B_X, C_X, D_X)\), \((A_Y, B_Y, C_Y, D_Y)\), \((A_Z, B_Z, C_Z, D_Z)\), and \((A_W, B_W, C_W, D_W)\), and must then compute \(H_{(K+1)..N}\), \(X_{(K+1)..M}\), \(Y_{(K+1)..M}\), \(Z_{(K+1)..M}\), and \(W_{(K+1)..M}\) as follows:

  \(H_i = ((A_H * H_{i-2} + B_H * H_{i-1} + C_H) \text{ modulo } D_H) + 1\)  for \(i > K\)
  \(X_i = ((A_X * X_{i-2} + B_X * X_{i-1} + C_X) \text{ modulo } D_X) + 1\)  for \(i > K\)
  \(Y_i = ((A_Y * Y_{i-2} + B_Y * Y_{i-1} + C_Y) \text{ modulo } D_Y) + 1\)  for \(i > K\)
  \(Z_i = ((A_Z * Z_{i-2} + B_Z * Z_{i-1} + C_Z) \text{ modulo } D_Z) + 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\)


# Constraints

\(1 \le T \le 90\)
\(2 \le N \le 1,000,000\)
\(2 \le M \le 1,000,000\)
\(2 \le K \le min(N, M)\)
\(0 \le A_H, B_H, C_H, A_X, B_X, C_X, A_Y, B_Y, C_Y, A_Z, B_Z, C_Z, A_W, B_W, C_W \le 1,000,000\)
\(1 \le D_H, D_Z, D_W \le 1,000,000\)
\(1 \le D_X, D_Y \le N\)
\(1 \le H_i \le D_H\)
\(1 \le X_i \le D_X\)
\(1 \le Y_i \le D_Y\)
\(1 \le Z_i \le D_Z\)
\(1 \le W_i \le D_W\)

The sum of \(N + M\) across all springs is at most 15,000,000.


# Input:

Input begins with an integer \(T\), the number of springs. For each spring there are 11 lines:

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

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

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

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

The fifth line contains the 4 space-separated integers \(A_X\), \(B_X\), \(C_X\), and \(D_X\).

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

The seventh line contains the 4 space-separated integers \(A_Y\), \(B_Y\), \(C_Y\), and \(D_Y\).

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

The ninth line contains the 4 space-separated integers \(A_Z\), \(B_Z\), \(C_Z\), and \(D_Z\).

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

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


# Output

For the \(i\)th spring, print a line containing *"Case #i: "*, followed by a single integer, the product of \(S_{1..M}\) modulo 1,000,000,007.


# Explanation of Sample

For the first spring, after the first earthquake, the spring looks as follows (with the 3 cm-long path which a water spider would follow from column 1 to column 2, or vice versa, indicated in red):

{{PHOTO_ID:825086724953069}}

After the second earthquake, the spring looks as follows (with the path now only being 2 cm long in either direction):

{{PHOTO_ID:2854957798069201}}

Therefore, \(S = [6, 4]\), and the final answer is (6 * 4) modulo 1,000,000,007 = 24.

For the second spring, \(S = [20, 8, 12]\), with the spring left in the following state after the final earthquake:

{{PHOTO_ID:2008456099296384}}

For the third spring, \(S = [222, 382, 110, 266, 136, 98]\).

For the fourth spring: 
- \(H = [37, 11, 18, 6, 34, 33, 14, 20, 13, 5]\)
- \(X = [2, 7, 3, 1, 5, 4, 9, 4, 8, 1, 6, 7]\) 
- \(Y = [2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1]\) 
- \(Z = [24, 38, 59, 64, 17, 36, 21, 22, 45, 8, 71, 4]\) 
- \(W = [16, 9, 55, 35, 58, 9, 4, 77, 55, 27, 10, 29]\)
- \(S = [2926, 3736, 650, 2754, 518, 6108, 5844, 330, 788, 3844, 7096, 9186]\)


Sample input:
5
2 2 2
2 3
0 0 0 100
2 1
0 0 0 2
1 1
0 0 0 2
4 1
0 0 0 100
1 3
0 0 0 100
3 3 3
1 2 4
0 0 0 100
2 3 1
0 0 0 3
1 1 2
0 0 0 3
2 4 6
0 0 0 100
1 5 5
0 0 0 100
6 6 6
13 4 7 11 2 5
0 0 0 100
1 3 6 1 1 4
0 0 0 6
1 2 1 1 3 2
0 0 0 6
13 9 5 4 10 12
0 0 0 100
8 2 9 3 6 11
0 0 0 100
10 12 2
37 11
1 2 3 45
2 7
2 3 4 9
2 1
3 4 5 4
24 38
4 5 6 78
16 9
5 6 7 87
100 200 3
470 104 185
213 20 226 692
76 35 8
499 768 377 92
23 9 12
880 205 286 31
165 249 43
883 477 453 674
385 68 409
853 105 54 410


Sample output:
Case #1: 24
Case #2: 1920
Case #3: 633021623
Case #4: 26104609
Case #5: 222201367


Solution: Let a line segment \((a, b)\) refer to a consecutive pair of columns with distinct heights \(a\) and \(b\), such that \(a < b\). If the column indices are \(i\) and \(i+1\), then we'll refer to \(i\) as the line segment's *position*.

We'll define the *weight* \(w\) of a line segment to be the number of spider paths which would cross it. If its index is \(i\), then \(w = i*(N-i)\). We'll say that each line segment has two separate *endpoints* with values \(a\) and \(b\), each with weight \(w\), and with weighted values \(w*a\) and \(w*b\).

When evaluating an \(S\) value for a water level \(W\), we'll define a *relevant line segment endpoint* as one with a value greater than \(W\). We'll start by computing the sum of relevant \(b\) endpoints' weighted values, and subtract the sum of relevant \(a\) endpoints' weighted values. There may be line segments for which we only added the \(b\) endpoint but didn't subtract the \(a\) endpoint (due to it being having a value no greater than \(W\)). To account for this, we'll take the sum of relevant \(b\) endpoints' weights, subtract the sum of relevant \(a\) endpoints' weights, multiply that difference by \(W\), and finally subtract that product to arrive at our final answer.

In order to compute the above values efficiently, we can maintain 4 Fenwick (binary indexed) trees, containing the \(a\) / \(b\) endpoints' weights / weighted values (in each case indexed by the endpoints' values). Assuming these have been maintained, we can compute each \(S\) value in \(O(log(N))\) time.

At first glance, it appears we'll need to perform up to \(O(NM)\) updates to these trees, given that up to \(N\) line segments may be affected by each of the \(M\) earthquakes. However, we can observe that setting the heights of an interval of columns \([L, R]\) causes all line segments at positions in \([L, R-1]\) to disappear, causes at most 2 new line segments (at positions \(L-1\) and \(R\)) to appear, and doesn't update any other line segments. Therefore, across all of the earthquakes, only \(O(N + M)\) line segments need to be updated, and we just need to not waste time iterating over positions not featuring line segments.

This can be done either by maintaining a set of intervals of equal-height columns (such that there's a line segment between each consecutive pair of intervals), or by maintaining a segment tree of column heights combined with a set of line segment positions. Either way, these data structures may be updated in amortized \(O(log(N))\) time per earthquake and allow us to only update the Fenwick trees described above for \(O(N + M)\) line segments overall. The total complexity is therefore \(O((N + M) log(N))\).


Code: // Spider Spring
// 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_map>
#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);
}

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;
}

#define MOD 1000000007
#define LIM 1000001

#define TVAL LL
#define TLAZY pair<LL,LL> // (set, increase)
#define TLIM 2100000

TVAL ZERO_VAL = 0;
TLAZY ZERO_LAZY = mp(0, 0);

struct SegTree
{
  void UpdateValForUpdateOrLazy(TVAL& a, TLAZY v)
  {
    if (v.x)
      a = v.x;
    if (v.y)
      a += v.y;
  }

  void UpdateLazyForUpdateOrLazy(TLAZY& a, TLAZY v)
  {
    if (v.x)
      a.x = v.x;
    if (v.y)
      a.y += v.y;
  }

  TVAL CombVals(TVAL v1, TVAL v2)
  {
    return(v1 + v2);
  }

  int N, sz;
  TVAL tree[TLIM];
  TLAZY lazy[TLIM];

  SegTree() {}

  SegTree(int _N)
  {
    Init(_N);
  }

  void Init(int _N)
  {
    N = _N;
    for (sz = 1; sz < N; sz <<= 1);
    Clear();
  }

  void Clear()
  {
    int i;
    Fox(i, sz << 1)
      tree[i] = ZERO_VAL;
    Fox(i, sz << 1)
      lazy[i] = ZERO_LAZY;
  }

  void Prop(int i)
  {
    TLAZY v = lazy[i];
    lazy[i] = ZERO_LAZY;
    UpdateValForUpdateOrLazy(tree[i], v);
    if (i < sz)
    {
      int c1 = i << 1, c2 = c1 + 1;
      UpdateLazyForUpdateOrLazy(lazy[c1], v);
      UpdateLazyForUpdateOrLazy(lazy[c2], v);
    }
  }

  void Comp(int i)
  {
    int c1 = i << 1, c2 = c1 + 1;
    tree[i] = CombVals(tree[c1], tree[c2]);
  }

  TVAL Query(
    int a, int b,
    int i = 1, int r1 = 0, int r2 = -1
  ) {
    if (r2 < 0)
      r2 = sz - 1;
    Prop(i);
    if (a <= r1 && r2 <= b)
      return(tree[i]);
    int m = (r1 + r2) >> 1, c = i << 1;
    TVAL ret = ZERO_VAL;
    if (a <= m)
      ret = CombVals(ret, Query(a, b, c, r1, m));
    if (b > m)
      ret = CombVals(ret, Query(a, b, c + 1, m + 1, r2));
    return(ret);
  }

  void Update(
    int a, int b,
    TLAZY v,
    int i = 1, int r1 = 0, int r2 = -1
  ) {
    if (r2 < 0)
      r2 = sz - 1;
    Prop(i);
    if (a <= r1 && r2 <= b)
    {
      UpdateLazyForUpdateOrLazy(lazy[i], v);
      Prop(i);
      return;
    }
    int m = (r1 + r2) >> 1, c = i << 1;
    if (a <= m)
      Update(a, b, v, c, r1, m);
    if (b > m)
      Update(a, b, v, c + 1, m + 1, r2);
    Prop(c), Prop(c + 1), Comp(i);
  }

  void UpdateOne(int i, TLAZY v) {
    i += sz;
    UpdateValForUpdateOrLazy(tree[i], v);
    while (i > 1)
    {
      i >>= 1;
      Comp(i);
    }
  }
};

int N, M, K;
int H[LIM], X[LIM], Y[LIM], Z[LIM], W[LIM];
set<int> LS;

// 0: height of column i
// 1: sum of A endpoint weights with endpoint value i
// 2: sum of A endpoint weighted values with endpoint value i
// 3: sum of B endpoint weights with endpoint value i
// 4: sum of B endpoint weighted values with endpoint value i
SegTree ST[5];

void UpdateHeights(int a, int b, int h)
{
  ST[0].Update(a, b, mp(h, 0));
}

void UpdateLineSegment(int i, int d) // d = 1 (add) / -1 (remove)
{
  if (i < 0 || i + 1 >= N)
    return;
  int a = ST[0].Query(i, i), b = ST[0].Query(i + 1, i + 1);
  if (a > b)
    swap(a, b);
  LL w = (LL)(i + 1) * (N - i - 1);
  ST[1].UpdateOne(a, mp(0, w % MOD * d));
  ST[2].UpdateOne(a, mp(0, a * w % MOD * d));
  ST[3].UpdateOne(b, mp(0, w % MOD * d));
  ST[4].UpdateOne(b, mp(0, b * w % MOD * d));
  if (d > 0)
    LS.insert(i);
  else
    LS.erase(i);
}

int ProcessCase()
{
  int i;
  // input
  Read(N), Read(M), Read(K);
  ReadSeq(H, N, K);
  ReadSeq(X, M, K);
  ReadSeq(Y, M, K);
  ReadSeq(Z, M, K);
  ReadSeq(W, M, K);
  // init segment trees, line segment set, and horizontal sum
  Fox(i, 5)
    ST[i].Init(!i ? N : LIM);
  LS.clear();
  LL horiz = 0;
  Fox(i, N)
  {
    UpdateHeights(i, i, H[i]);
    UpdateLineSegment(i - 1, 1);
    horiz = (horiz + (LL)i * (N - i)) % MOD;
  }
  // process events
  int ans = 1;
  Fox(i, M)
  {
    // update
    int x = X[i] - 1;
    int y = min(x + Y[i], N) - 1;
    int z = Z[i];
    auto I = LS.lower_bound(x - 1);
    while (I != LS.end() && *I <= y)
    {
      int k = *I;
      I++;
      UpdateLineSegment(k, -1);
    }
    UpdateHeights(x, y, z);
    UpdateLineSegment(x - 1, 1);
    UpdateLineSegment(y, 1);
    // query
    int w = W[i];
    LL d1 = ST[4].Query(w + 1, LIM - 1) - ST[2].Query(w + 1, LIM - 1);
    LL d2 = ST[3].Query(w + 1, LIM - 1) - ST[1].Query(w + 1, LIM - 1);
    LL vert = ((d1 - d2 % MOD * w) % MOD + MOD) % MOD;
    ans = (LL)ans * (horiz + vert) * 2 % MOD;
  }
  return(ans);
}

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