#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
#define int long long
template<typename T>
using vec = vector<T>;
template<typename it>
struct PrefixSum {
using T = typename remove_reference<decltype(*declval<it>())>::type;
vector<T> pref;
PrefixSum() = default;
PrefixSum(it first, it last) {
pref = vector<T>(distance(first, last) + 1);
for (int i = 0; i < pref.size(); i++)
pref[i] = (i == 0 ? 0 : pref[i - 1]) + *(first + i);
}
T operator()(int l, int r) {
assert(l >= 0 && r < pref.size());
assert(l <= r);
if (l > r)
return 0;
if (l == 0)
return pref[r];
return pref[r] - pref[l - 1];
}
};
std::vector<int> mosaic(std::vector<i32> X, std::vector<i32> Y,
std::vector<i32> T, std::vector<i32> B,
std::vector<i32> L, std::vector<i32> R) {
int n = (int) X.size();
if (n < 3) {
vec<vec<bool>> a(n, vec<bool>(n, false));
for (int i = 0; i < n; i++) {
a[0][i] = X[i];
a[i][0] = Y[i];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
a[i][j] = !(a[i - 1][j] | a[i][j - 1]);
}
}
vec<int> ans;
int q = T.size();
while (q--) {
int sum = 0;
for (int i = T[q]; i <= B[q]; i++) {
for (int j = L[q]; j <= R[q]; j++) {
if (a[i][j]) sum++;
}
}
ans.push_back(sum);
}
reverse(ans.begin(), ans.end());
return ans;
}
{
// vec<vec<bool>> a(n, vec<bool>(n, false));
// for (int i = 0; i < n; i++) {
// a[0][i] = X[i];
// a[i][0] = Y[i];
// }
// for (int i = 1; i < n; i++) {
// for (int j = 1; j < n; j++) {
// a[i][j] = !(a[i - 1][j] | a[i][j - 1]);
// }
// }
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cout << a[i][j] << " ";
// }
// cout << endl;
// }
}
vec<vec<bool>> top(3, vec<bool>(n, false));
for (int i = 0; i < n; i++) {
top[0][i] = X[i];
}
top[1][0] = Y[1];
top[2][0] = Y[2];
for (int i = 1; i < n; i++) {
for (int j = 1; j < 3; j++) {
top[j][i] = !(top[j - 1][i] || top[j][i - 1]);
}
}
vec<vec<bool>> left(n, vec<bool>(3, false));
for (int i = 0; i < n; i++) {
left[i][0] = Y[i];
}
left[0][1] = X[1];
left[0][2] = X[2];
for (int i = 1; i < n; i++) {
for (int j = 1; j < 3; j++) {
left[i][j] = !(left[i - 1][j] || left[i][j - 1]);
}
}
vec<vec<int>> topPref(3, vec<int>(n, 0));
vec<vec<int>> leftPref(n, vec<int>(3, 0));
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
topPref[i][j] = top[i][j];
if (i)
topPref[i][j] += topPref[i - 1][j];
if (j)
topPref[i][j] += topPref[i][j - 1];
if (i && j)
topPref[i][j] -= topPref[i - 1][j - 1];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
leftPref[i][j] = left[i][j];
if (i)
leftPref[i][j] += leftPref[i - 1][j];
if (j)
leftPref[i][j] += leftPref[i][j - 1];
if (i && j)
leftPref[i][j] -= leftPref[i - 1][j - 1];
}
}
vec<int> top_a(n - 2, 0);
for (int i = 2; i < n; i++) {
top_a[i - 2] = top[2][i];
}
vec<int> top_a_id = top_a;
for (int i = (int) top_a.size() - 1; i >= 0; i--) {
top_a_id[i] *= (int) (top_a.size() - i);
}
vec<int> left_a(n - 3, 0);
for (int i = 3; i < n; i++) {
left_a[i - 3] = left[i][2];
}
vec<int> left_a_id = left_a;
for (int i = (int) left_a.size() - 1; i >= 0; i--) {
left_a_id[i] *= (int) (left_a.size() - i);
}
PrefixSum top_a_ps(top_a.begin(), top_a.end());
PrefixSum left_a_ps(left_a.begin(), left_a.end());
PrefixSum top_a_id_ps(top_a_id.begin(), top_a_id.end());
PrefixSum left_a_id_ps(left_a_id.begin(), left_a_id.end());
auto get = [&](int i, int j) {
if (i < 0 || j < 0 || i >= n || j >= n) {
return 0LL;
}
if (i <= 2) {
return topPref[i][j];
}
if (j <= 2) {
return leftPref[i][j];
}
int ans = topPref[1][j] + leftPref[i][1] - topPref[1][1];
{
int start = 0;
if (j > i) {
ans += top_a_ps(0, j - i - 1) * (i - 1);
start = j - i;
}
ans += top_a_id_ps(start, j - 2) - top_a_ps(start, j - 2) * ((int) top_a.size() - (j - 2) - 1);
}
{
int start = 0;
if (i - 1 > j) {
ans += left_a_ps(0, i - j - 2) * (j - 1);
start = i - j - 1;
}
ans += left_a_id_ps(start, i - 3) - left_a_ps(start, i - 3) * ((int) left_a.size() - (i - 3) - 1);
}
return ans;
};
int q = (int) T.size();
vec<int> ans;
while (q--) {
auto [t, b, l, r] = tuple(T[q], B[q], L[q], R[q]);
ans.push_back(get(b, r) - get(t - 1, r) - get(b, l - 1) + get(t - 1, l - 1));
}
reverse(ans.begin(), ans.end());
return ans;
}
