#include <vector> #include <algorithm> #include <iostream> using namespace std; // We use long long for sums to avoid overflow (N*N can be 4*10^10) typedef long long ll; struct GridSolver { int N; // Prefix sums for the diagonal values // S0[k] = sum of V[i] for i <= k // S1[k] = sum of i * V[i] for i <= k // Indices for V range from -(N-1) to (N-1). // We offset them by adding N. vector<ll> S0, S1; // Prefix sums for Row 0 and Col 0 vector<int> PX, PY; void build(int n, const vector<int>& X, const vector<int>& Y) { N = n; // 1. Compute Row 1 and Col 1 values (for the grid starting at 1,1) // Global (1, j) depends on Global (0, j) and Global (1, j-1) // Global (i, 1) depends on Global (i-1, 1) and Global (i, 0) vector<int> R1(N), C1(N); // Compute (1, 1) int val_1_1 = ((X[1] == 0) && (Y[1] == 0)) ? 1 : 0; R1[1] = val_1_1; C1[1] = val_1_1; for (int j = 2; j < N; ++j) { R1[j] = ((X[j] == 0) && (R1[j-1] == 0)) ? 1 : 0; } for (int i = 2; i < N; ++i) { C1[i] = ((C1[i-1] == 0) && (Y[i] == 0)) ? 1 : 0; } // 2. Build V array // V[k] corresponds to diagonal c - r = k // range of k: -(N-1) to (N-1) // Size needed: 2*N int offset = N; int v_size = 2 * N + 5; vector<int> V(v_size, 0); // Center k=0 is (1,1) -> R1[1] V[0 + offset] = R1[1]; // Positive k: (1, 1+k) -> R1[1+k] for (int k = 1; k < N; ++k) { if (1 + k < N) V[k + offset] = R1[1+k]; } // Negative k: (1-k, 1) -> C1[1-k]. Let k = -d. (1+d, 1) -> C1[1+d] for (int k = -1; k > -N; --k) { if (1 - k < N) V[k + offset] = C1[1-k]; } // 3. Build Prefix Sums 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; // The actual k value is (i - offset) ll k = i - offset; S0[i] = prev0 + val; S1[i] = prev1 + k * val; } // 4. Prefix sums for X and Y 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]; } 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 just in case, though logic should prevent OOB i1 = max(0, i1); i2 = min((int)S0.size()-1, i2); ll v2 = S0[i2]; ll v1 = (i1 > 0) ? S0[i1-1] : 0; return v2 - v1; } 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); ll v2 = S1[i2]; ll v1 = (i1 > 0) ? S1[i1-1] : 0; return v2 - v1; } // Calculate sum of diagonals in global rect [1..rows] x [1..cols] // Note: rows, cols are counts. // e.g. rows=2 means global rows 1 and 2 are included. ll calc_grid_sum(int rows, int cols) { if (rows <= 0 || cols <= 0) return 0; ll total = 0; if (rows <= cols) { // Zone 1: [1-rows, 0]. Count = rows + k total += (ll)rows * get_S0(1-rows, 0) + get_S1(1-rows, 0); // Zone 2: [1, cols-rows]. Count = rows total += (ll)rows * get_S0(1, cols-rows); // Zone 3: [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: [1-rows, cols-rows]. Count = rows + k total += (ll)rows * get_S0(1-rows, cols-rows) + get_S1(1-rows, cols-rows); // Zone 2: [cols-rows+1, 0]. Count = cols total += (ll)cols * get_S0(cols-rows+1, 0); // Zone 3: [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; } }; vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) { int N = X.size(); int Q = T.size(); GridSolver solver; solver.build(N, X, Y); 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: Row 0 if (t == 0) { ans += solver.query_X(l, r); } // Part B: Col 0 (excluding (0,0) if already counted) if (l == 0) { // If we counted row 0, we counted (0,0). So start from row 1. // But query range for Y is [t, b]. // Intersection of [t, b] and [1, N-1]. int y_start = max(1, t); if (y_start <= b) { ans += solver.query_Y(y_start, b); } } // Part C: Grid [1..N-1] x [1..N-1] // Intersection of query [t, b] x [l, r] with [1, N-1] x [1, N-1] int t_prime = max(1, t); int l_prime = max(1, l); if (t_prime <= b && l_prime <= r) { // We need sum in [t_prime, b] x [l_prime, r] // Maps to calc_grid_sum args: calc(row_idx, col_idx) // Indices in calc are inclusive max row/col // Global row index i maps to calc arg i. 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; }