#include <vector> #include <algorithm> #include <iostream> using namespace std; typedef long long ll; struct GridSolver { int N; // S0[i]: Prefix sum of V[k] // S1[i]: Prefix sum of k * V[k] // Indices are offset by N to handle negative diagonal indices. // Index i corresponds to diagonal k = i - N. vector<ll> S0, S1; // Prefix sums for input arrays X (Row 0) and Y (Col 0) vector<ll> PX, PY; void build(int n, const vector<int>& X, const vector<int>& Y) { N = n; // --- Step 1: Compute Row 1 and Column 1 --- // These serve as the "generators" for the rest of the grid (i,j >= 1). vector<int> R1(N), C1(N); // Only proceed if N > 1, as the inner grid exists only for N >= 2 if (N > 1) { // Compute corner (1,1). Logic: NOR(Top, Left) -> NOR(X[1], Y[1]) int val_1_1 = ((X[1] == 0) && (Y[1] == 0)) ? 1 : 0; R1[1] = val_1_1; C1[1] = val_1_1; // Fill Row 1 for (int j = 2; j < N; ++j) { // Top is X[j], Left is R1[j-1] R1[j] = ((X[j] == 0) && (R1[j-1] == 0)) ? 1 : 0; } // Fill Column 1 for (int i = 2; i < N; ++i) { // Top is C1[i-1], Left is Y[i] C1[i] = ((C1[i-1] == 0) && (Y[i] == 0)) ? 1 : 0; } } // --- Step 2: Build Diagonal Value Array V --- // V[k] stores the value for diagonal j - i = k. // Valid k for inner grid ranges from -(N-2) to (N-2). // To cover all potential query ranges safely, we size for roughly -N to N. int offset = N; int v_size = 2 * N + 5; vector<int> V(v_size, 0); if (N > 1) { // k=0 corresponds to (1,1) V[0 + offset] = R1[1]; // k > 0: Upper triangular part (Row 1). k goes up to N-2. for (int k = 1; k < N; ++k) { if (1 + k < N) V[k + offset] = R1[1+k]; } // k < 0: Lower triangular part (Col 1). k goes down to -(N-2). for (int k = -1; k > -N; --k) { if (1 - k < N) V[k + offset] = C1[1-k]; } } // --- Step 3: Compute Prefix Sums for Diagonals --- S0.assign(v_size, 0); S1.assign(v_size, 0); for (int i = 0; i < v_size; ++i) { ll val = V[i]; ll prev0 = (i > 0) ? S0[i-1] : 0; ll prev1 = (i > 0) ? S1[i-1] : 0; ll k = i - offset; // Actual diagonal index S0[i] = prev0 + val; S1[i] = prev1 + k * val; } // --- Step 4: Prefix Sums for Boundaries (Row 0, Col 0) --- PX.assign(N, 0); PY.assign(N, 0); PX[0] = X[0]; for(int i=1; i<N; ++i) PX[i] = PX[i-1] + X[i]; PY[0] = Y[0]; for(int i=1; i<N; ++i) PY[i] = PY[i-1] + Y[i]; } // Helper: Range sum for S0. range [k1, k2] inclusive. ll get_S0(int k1, int k2) { int offset = N; int i1 = k1 + offset; int i2 = k2 + offset; if (i1 > i2) return 0; // Clamp indices to the stored range. // V is effectively 0 outside valid indices, so this is safe. i1 = max(0, i1); i2 = min((int)S0.size()-1, i2); if (i1 > i2) return 0; // Double check after clamping ll v2 = S0[i2]; ll v1 = (i1 > 0) ? S0[i1-1] : 0; return v2 - v1; } // Helper: Range sum for S1. range [k1, k2] inclusive. ll get_S1(int k1, int k2) { int offset = N; int i1 = k1 + offset; int i2 = k2 + offset; if (i1 > i2) return 0; i1 = max(0, i1); i2 = min((int)S1.size()-1, i2); if (i1 > i2) return 0; ll v2 = S1[i2]; ll v1 = (i1 > 0) ? S1[i1-1] : 0; return v2 - v1; } // Calculates sum of black tiles in the global rectangle defined by corner (rows, cols) // relative to the inner grid start. // Effectively sums V[c-r] for 1 <= r <= rows, 1 <= c <= cols. ll calc_grid_sum(int rows, int cols) { if (rows <= 0 || cols <= 0) return 0; ll total = 0; // We split the summation of count(k) * V[k] into 3 linear zones. if (rows <= cols) { // Zone 1: Ascending count (bottom-left triangle) // Range: [1-rows, 0]. Count = rows + k total += (ll)rows * get_S0(1-rows, 0) + get_S1(1-rows, 0); // Zone 2: Constant count (middle trapezoid) // Range: [1, cols-rows]. Count = rows total += (ll)rows * get_S0(1, cols-rows); // Zone 3: Descending count (top-right triangle) // Range: [cols-rows+1, cols-1]. Count = cols - k total += (ll)cols * get_S0(cols-rows+1, cols-1) - get_S1(cols-rows+1, cols-1); } else { // Zone 1: Ascending count // Range: [1-rows, cols-rows]. Count = rows + k total += (ll)rows * get_S0(1-rows, cols-rows) + get_S1(1-rows, cols-rows); // Zone 2: Constant count // Range: [cols-rows+1, 0]. Count = cols total += (ll)cols * get_S0(cols-rows+1, 0); // Zone 3: Descending count // Range: [1, cols-1]. Count = cols - k total += (ll)cols * get_S0(1, cols-1) - get_S1(1, cols-1); } return total; } ll query_X(int L, int R) { if (L > R) return 0; ll v2 = PX[R]; ll v1 = (L > 0) ? PX[L-1] : 0; return v2 - v1; } ll query_Y(int T, int B) { if (T > B) return 0; ll v2 = PY[B]; ll v1 = (T > 0) ? PY[T-1] : 0; return v2 - v1; } }; std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> L, std::vector<int> R) { int N = X.size(); int Q = T.size(); GridSolver solver; solver.build(N, X, Y); std::vector<long long> results(Q); for (int k = 0; k < Q; ++k) { int t = T[k]; int b = B[k]; int l = L[k]; int r = R[k]; ll ans = 0; // Part A: Intersection with Row 0 if (t == 0) { ans += solver.query_X(l, r); } // Part B: Intersection with Col 0 // We must avoid double counting (0,0) if it was included in Part A. // If Part A ran (t=0), then (0,0) is counted if l=0. // We simply take the column sum from row max(1, t) to b. if (l == 0) { int y_start = max(1, t); if (y_start <= b) { ans += solver.query_Y(y_start, b); } } // Part C: Intersection with Inner Grid (rows 1..N-1, cols 1..N-1) int t_prime = max(1, t); int l_prime = max(1, l); if (t_prime <= b && l_prime <= r) { // calc_grid_sum(rows, cols) sums the rectangle of size rows x cols starting at inner (1,1). // This maps to global range [1, rows] x [1, cols]. // We want global range [t_prime, b] x [l_prime, r]. ans += solver.calc_grid_sum(b, r) - solver.calc_grid_sum(t_prime - 1, r) - solver.calc_grid_sum(b, l_prime - 1) + solver.calc_grid_sum(t_prime - 1, l_prime - 1); } results[k] = ans; } return results; }