Problem: circular_circles (2020 round2)

Cyrus has come across a curious sight — an undirected, weighted graph with \(N*M\) nodes (numbered from \(0\) to \( N*M - 1\)) and \(N*M + N\) edges (numbered from \(0\) to \(N*M + N - 1\)). Each edge initially has a weight of \(1\).

What makes this graph so curious is its shape. The nodes are arranged in \(N\) "circles" of \(M\) nodes each. Nodes \(0..(M - 1)\) are in the first circle, nodes \(M..(2*M - 1)\) are in the second, and so on. In each circle, the nodes are arranged in clockwise order (ordered by increasing node number).

The first \(N*M\) edges lie within circles, with \(M\) edges per circle. Edges \(0..(M - 1)\) lie within the first circle, edges \(M..(2*M - 1)\) lie within the second, and so on. In each circle, its first (lowest-numbered) edge connects the circle's first and second nodes, its second edge connects its second and third nodes, and so on, with its final edge connecting its final and first nodes.

There are \(N\) more edges (edges \((N*M)..(N*M + N - 1)\)) connecting the \(N\) circles into what might be considered an additional circle. Each circle \(i\) has two "connection points", the first of which is its \((X_i+1)\)st node (that is, node \(M*i + X_i\)), and the second of which is its \((Y_i+1)\)st node (node \(M*i + Y_i\)). \(X_i\) and \(Y_i\) are not necessarily distinct. The \(i\)th of the \(N\) final edges connects the second connection point of circle \(i\) and the first connection point of circle \(((i+1)\text{ modulo }N)\). That is, there's an edge between nodes \(M*0 + Y_0\) and \(M*1 + X_1\), another between \(M*1 + Y_1\) and \(M*2 + X_2\), and so on, with the final edge connecting nodes \(M*(N-1) + Y_{N-1}\) and \(M*0 + X_0\).

For example, if \(N = 3\), \(M = 3\), \(X = [0, 2, 1]\), and \(Y = [1, 2, 0]\), the graph would look as follows (with the first \(N*M\) edges indicated in blue, and the last \(N\) in red):

{{PHOTO_ID:316300889650982}}

Cyrus was hoping to practice computing the [minimum spanning tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree) of this graph, but it's starting to change before his very eyes! \(E\) events are about to occur on the graph (numbered from \(0\) to \(E-1\)), one after another. Event \(i\) will cause the weight of edge \(I_i\) to become \(W_i\). When an edge's weight changes, it will remain at its new value for future events (until changed again).

Let \(V_i\) be the weight of the graph's minimum spanning tree after the first \(i\) events. Help Cyrus compute the product of \(V_{1..E}\). As this product may be very large, you should only compute its value 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 \(X_{0..(K-1)}\), \(Y_{0..(K-1)}\), \(I_{0..(K-1)}\), and \(W_{0..(K-1)}\), as well as the four triples of constants \((A_X, B_X, C_X)\), \((A_Y, B_Y, C_Y)\), \((A_I, B_I, C_I)\), and \((A_W, B_W, C_W)\), and must then compute \(X_{K..(N-1)}\), \(Y_{K..(N-1)}\), \(I_{K..(E-1)}\), and \(W_{K..(E-1)}\) as follows:

\(X_i = (A_X * X_{i-2} + B_X * X_{i-1} + C_X)\text{ modulo }M\) for \(i \ge K\)
\(Y_i = (A_Y * Y_{i-2} + B_Y * Y_{i-1} + C_Y)\text{ modulo }M\) for \(i \ge K\)
\(I_i = (A_I * I_{i-2} + B_I * I_{i-1} + C_I)\text{ modulo }(N*M + N)\) for \(i \ge K\)
\(W_i = (A_W * W_{i-2} + B_W * W_{i-1} + C_W)\text{ modulo }1,000,000,000\) for \(i \ge K\)


# Input

Input begins with an integer \(T\), the number of graphs. For each graph, there are 9 lines:

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

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

The third line contains the 3 space-separated integers \(A_X\), \(B_X\), and \(C_X\).

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

The fifth line contains the 3 space-separated integers \(A_Y\), \(B_Y\), and \(C_Y\).

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

The seventh line contains the 3 space-separated integers \(A_I\), \(B_I\), and \(C_I\).

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

The ninth line contains the 3 space-separated integers \(A_W\), \(B_W\), and \(C_W\).

# Output

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

# Constraints

\(1 \le T \le 90\)
\(3 \le N, M \le 1,000,000\)
\(N*M + N \le 1,000,000\)
\(2 \le E \le 1,000,000\)
\(2 \le K \le min(N, E)\)
\(0 \le A_X, B_X, C_X, A_Y, B_Y, C_Y, A_I, B_I, C_I, A_W, B_W, C_W \le 1,000,000,000\)
\(0 \le X_i, Y_i < M\)
\(0 \le I_i < N*M + N\)
\(0 \le W_i < 1,000,000,000\)

The sum of \(N*M + E\) across all \(T\) graphs is at most 20,000,000.

# Explanation of Sample

**For the first graph:**

- \(X = [0, 2, 1]\)
- \(Y = [1, 2, 0]\)
- \(I = [9, 10, 11]\)
- \(W = [1, 1, 1]\)

Each event causes an edge weight to remain equal to \(1\). Therefore, the graph looks as follows, both initially and after all three events:

{{PHOTO_ID:2720312131621256}}
  
A minimum spanning tree on this graph must involve 8 weight-1 edges. Therefore, \(V = [8, 8, 8]\), and the final answer is \((8 * 8 * 8)\text{ modulo 1,000,000,007} = 512\).

**For the second graph:**

- \(X = [0, 2, 1]\)
- \(Y = [1, 2, 0]\)
- \(I = [6, 10, 2, 5, 3, 2, 10, 1]\)
- \(W = [0, 2, 2, 3, 3, 4, 4, 5]\)

After the eighth and final event, the graph looks as follows, with one possible minimum spanning tree highlighted:

{{PHOTO_ID:1530362313804065}}

For this graph, \(V = [7, 7, 7, 7, 9, 9, 9, 12]\).

**For the third graph:**

- \(X = [1, 2, 0]\)
- \(Y = [1, 1, 0]\)
- \(I = [14, 12, 1, 3, 5, 7, 9, 11, 13, 0]\)
- \(W = [11, 0, 6, 9, 12, 15, 18, 21, 24, 27]\)

For this graph, \(V = [11, 10, 10, 15, 15, 25, 25, 42, 53, 61]\).

**For the fourth graph:**

- \(X = [4, 1, 3, 4, 0]\)
- \(Y = [0, 3, 3, 0, 0]\)


Sample input:
5
3 3 3 3
0 2 1
0 0 0
1 2 0
0 0 0
9 10 11
0 0 0
1 1 1
0 0 0
3 3 8 3
0 2 1
0 0 0
1 2 0
0 0 0
6 10 2
1 2 3
0 2 2
1 0 1
3 4 10 3
1 2 0
0 0 0
1 1 0
0 0 0
14 12 1
0 1 2
11 0 6
0 1 3
5 6 40 2
4 1
3 2 1
0 3
1 2 3
27 14
4 5 6
3192874 490177205
6 5 4
20 8 100 2
6 2
31 92 44
6 7
61 40 16
43 12
28 6 52
47 66
91 86 28


Sample output:
Case #1: 512
Case #2: 21003948
Case #3: 396727972
Case #4: 166299874
Case #5: 849275180


Solution: We can observe that the weight of the minimum spanning tree is equal to the sum of all edge weights in the graph (*Quantity 1*), minus the weight of one removed edge per circle (*Quantity 2*), minus the weight of one additional removed edge somewhere in the graph (*Quantity 3*).

For *Quantity 3*, the additional removed edge may either be any inter-circle edge, or *potentially* a second edge within some circle. There are two categories of circles:

- If \(X_i = Y_i\), no two of its edges can be validly removed (without disconnecting the graph).
- Otherwise, if \(X_i \ne Y_i\), the circle can be considered to have two "halves" (the paths connecting its \(X_i\)th and \(Y_i\)th nodes clockwise and counterclockwise), such that up to one edge may be validly removed from *each* half (without disconnecting the graph).

For each circle \(i\), we'll define three values of interest:

- Let \(R_i\) be the maximum weight of any edge within the circle. This will help with computing *Quantity 2*.
- Let \(P_i\) be the maximum possible combined weight of any validly-removable pair of edges within the circle (if any). If \(X_i = Y_i\) (meaning that only one of its edges may be removed), we'll let \(P_i = R_i\) instead.
- Let \(D_i = P_i - R_i\). The represents the additional amount by which the minimum spanning tree's weight can be decreased if two edges are removed from the circle, and will help with computing *Quantity 3*.

Then, for each circle \(i\), we'll maintain:

- An ordered multiset of all edge weights within it (used to compute \(R_i\)).
- If \(X_i \ne Y_i\), two additional ordered multisets containing all edge weights in each of its halves (used to compute \(D_i\)).

On top of that, we'll globally maintain:

- The sum of all edge weights in the graph (*Quantity 1*).
- The sum of all circles' \(R_i\) values (equivalent to *Quantity 2*).
- An ordered multiset of all circles' \(D_i\) values, and another containing all inter-circle edge weights (combined to compute *Quantity 3*).

Each event (and initial edge) requires us to update just a constant number of the above values and multisets, each taking logarithmic time (provided that the multisets are implemented using BBSTs). Therefore, this solution has a time complexity of \(O((NM + E) (log(N) + log(M)))\).



Code: // Circular Circles
// 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);
}

#define LIM 1000001
#define MOD 1000000007

int N, M, E, K;
int X[LIM], Y[LIM], I[LIM], W[LIM], EW[LIM];

LL sumR;
multiset<int> CS[LIM]; // CS[i] = edge weights in circle i
multiset<int> HS[LIM][2]; // HS[i][j] = edge weights in half j of circle i
multiset<int> DS; // DS = circles' D values
multiset<int> IS; // IS = inter-circle edge weights

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

void UpdateSet(multiset<int>& S, int v1, int v2)
{
  assert(*S.find(v1) == v1);
  S.erase(S.find(v1));
  S.insert(v2);
}

int GetCircleR(int i) { return(*CS[i].rbegin()); }

int GetCircleD(int i) { return(*HS[i][0].rbegin() + *HS[i][1].rbegin() - *CS[i].rbegin()); }

int GetHalf(int i, int j) { return(X[i] <= j && j < Y[i] ? 0 : 1); }

void UpdateCircleEdge(int i, int j, int w1, int w2)
{
  int r1 = GetCircleR(i), d1 = GetCircleD(i);
  UpdateSet(CS[i], w1, w2);
  UpdateSet(HS[i][GetHalf(i, j)], w1, w2);
  int r2 = GetCircleR(i), d2 = GetCircleD(i);
  sumR += r2 - r1;
  UpdateSet(DS, d1, d2);
}

int ProcessCase()
{
  int i, j;
  LL sumW;
  // init
  DS.clear(), IS.clear();
  Fox(i, N)
    CS[i].clear(), HS[i][0].clear(), HS[i][1].clear();
  // input
  Read(N), Read(M), Read(E), Read(K);
  ReadSeq(X, N, K, M);
  ReadSeq(Y, N, K, M);
  ReadSeq(I, E, K, N * M + N);
  ReadSeq(W, E, K, INF);
  // initialize edge info
  sumW = N * M + N;
  sumR = N;
  Fox(i, N * M + N)
    EW[i] = 1;
  Fox(i, N)
  {
    if (X[i] > Y[i])
      swap(X[i], Y[i]);
    Fox(j, 2)
      HS[i][j].insert(0);
    Fox(j, M)
    {
      CS[i].insert(1);
      HS[i][GetHalf(i, j)].insert(1);
    }
    DS.insert(GetCircleD(i));
    IS.insert(1);
  }
  // process events
  int ans = 1;
  Fox(i, E)
  {
    j = I[i];
    int w1 = EW[j], w2 = W[i];
    EW[j] = w2;
    sumW += w2 - w1;
    if (j < N * M)
      UpdateCircleEdge(j / M, j % M, w1, w2);
    else
      UpdateSet(IS, w1, w2);
    LL cur = sumW - sumR - max(*DS.rbegin(), *IS.rbegin());
    ans = 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);
}