#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "/home/fv3/prog/debug/debug.h"
#else
#define debug(...) 42
#endif
using ll = long long;
vector<ll> mosaic(vector<int> X, vector<int> Y,
vector<int> T, vector<int> B,
vector<int> L, vector<int> R) {
const int n = X.size();
if (n <= 3) {
vector<vector<int>> grid(n, vector<int>(n));
swap(grid[0], X);
for (int i = 0; i < n; i++) {
grid[0][i] = Y[i];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
grid[i][j] = !(grid[i-1][j] || grid[i][j-1]);
}
}
int q = int(T.size());
vector<ll> res(q);
for (int qq = 0; qq < q; qq++) {
int l = L[qq], r = R[qq], t = T[qq], b = B[qq];
int sum = 0;
for (int i = l; i <= r; i++) {
for (int j = t; j <= b; j++) {
sum += grid[i][j];
}
}
res[qq] = sum;
}
return res;
}
vector<vector<int>> grid(n, vector<int>(3));
swap(grid[0], X);
for (int i = 0; i < n; i++) {
grid[i][0] = Y[i];
}
for (int i = 1; i < min(3, n); i++) {
grid[i].resize(n);
for (int j = 1; j < n; j++) {
grid[i][j] = !(grid[i-1][j] || grid[i][j-1]);
}
}
for (int i = 3; i < n; i++) {
for (int j = 1; j < 3; j++) {
grid[i][j] = !(grid[i-1][j] || grid[i][j-1]);
}
}
vector<int> diag(2*n-1);
for (int i = 2; i < n; i++) {
if (grid[2][i]) {
diag[i - 2 + n - 1] = 1;
}
if (grid[i][2]) {
diag[2 - i + n - 1] = 1;
}
}
vector<ll> diag_ps(2*n);
for (int i = 0; i < 2*n-1; i++) {
diag_ps[i+1] = diag_ps[i] + diag[i];
}
vector<ll> incr_diag_ps(2*n);
for (int i = 0; i < 2*n-1; i++) {
incr_diag_ps[i+1] = incr_diag_ps[i] + 1ll * (i+1) * diag[i];
}
vector<vector<int>> ps_x(3, vector<int>(n+1)), ps_y(n+1, vector<int>(3));
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
ps_x[i][j+1] = ps_x[i][j] + grid[i][j];
ps_y[j+1][i] = ps_y[j][i] + grid[j][i];
}
}
int q = (int)T.size();
vector<ll> C(q, 0);
for (int qq = 0; qq < q; qq++) {
int l = L[qq], r = R[qq], t = T[qq], b = B[qq];
if (min(r, b) < 3) {
if (r < 3) {
for (int i = l; i <= r; i++) {
C[qq] += ps_y[b+1][i] - ps_y[t][i];
}
} else {
for (int i = t; i <= b; i++) {
C[qq] += ps_x[i][r+1] - ps_x[i][l];
}
}
continue;
}
if (l < 3) {
for (int i = l; i < 3; i++) {
C[qq] += ps_y[b+1][i] - ps_y[t][i];
}
l = 3;
}
if (t < 3) {
for (int i = t; i < 3; i++) {
C[qq] += ps_x[i][r+1] - ps_x[i][l];
}
t = 3;
}
auto Solve = [&](int row, int col) -> ll {
int mn = min(row, col);
int mx = max(row, col);
int diag_l = n - row - 1;
int diag_ml = diag_l + mn;
int diag_mr = diag_ml + (mx - mn);
int diag_r = col + n - 1;
ll res = 0;
res += 1ll * (mn + 1) * (diag_ps[diag_mr + 1] - diag_ps[diag_ml]);
res += incr_diag_ps[diag_ml] - 1ll * diag_ps[diag_ml] * diag_l;
res += 1ll * (diag_r + 2) * (diag_ps[diag_r + 1] - diag_ps[diag_mr + 1]);
res -= incr_diag_ps[diag_r + 1] - incr_diag_ps[diag_mr + 1];
return res;
};
C[qq] += Solve(b, r) - Solve(b, l-1) - Solve(t-1, r) + Solve(t-1, l-1);
}
return C;
}
//#include "grader.cpp"
