#include "mosaic.h"
#include <iostream>
#include <vector>
#include <map>
#define ll long long
using namespace std;
map <ll, ll> mp;
vector <ll> F, ps, V, ps1, ps2, ps3, rps1;
ll solve(ll x, ll y) {
ll res = ps2[mp[-x]] - (mp[min(x, y)-x] == ps2.size()-1 ? 0 : (ps2[mp[min(x, y)-x]+1] + rps1[mp[min(x, y)-x]+1] * min(x+1, y+1)));
res += ps3[mp[y]] - (mp[y-min(x, y)] == 0 ? 0 : (ps3[mp[y-min(x, y)]-1]) + ps1[mp[y-min(x, y)]-1] * min(x+1, y+1));
if (mp[y-min(x, y)]-1 >= mp[min(x, y)-x]+1) res += (ps1[mp[y-min(x, y)]-1] - ps1[mp[min(x, y)-x]]) * min(x+1, y+1);
if (x == y) res -= V[mp[0]] * min(x+1, y+1);
return res;
}
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) {
F.clear();
ps.clear();
V.clear();
ps1.clear();
ps2.clear();
ps3.clear();
rps1.clear();
ll n = X.size(), q = T.size();
F.resize(q);
ps.resize(n);
for (int i=0; i<n; ++i) ps[i] = X[i] + (i == 0 ? 0 : ps[i-1]);
for (int i=0; i<q; ++i) {
if (T[i] == 0) F[i] += ps[R[i]] - (L[i] == 0 ? 0 : ps[L[i]-1]);
}
for (int i=0; i<n; ++i) ps[i] = Y[i] + (i == 0 ? 0 : ps[i-1]);
for (int i=0; i<q; ++i) {
if (L[i] == 0) F[i] += ps[B[i]] - (T[i] == 0 ? ps[0] : ps[T[i]-1]);
T[i] = max(T[i], 1);
L[i] = max(L[i], 1);
}
for (int i=1; i<n; ++i) {
X[i] = (((i == 1 ? Y[1] : X[i-1]) == 0 && X[i] == 0) ? 1 : 0);
}
Y[1] = X[1];
for (int i=2; i<n; ++i) {
Y[i] = ((Y[i-1] == 0 && Y[i] == 0) ? 1 : 0);
}
for (int i=1; i<n; ++i) ps[i] = X[i] + (i == 1 ? 0 : ps[i-1]);
for (int i=0; i<q; ++i) {
if (T[i] > B[i] || L[i] > R[i]) continue;
if (T[i] == 1) F[i] += ps[R[i]] - (L[i] == 1 ? 0 : ps[L[i]-1]);
}
for (int i=1; i<n; ++i) ps[i] = Y[i] + (i == 1 ? 0 : ps[i-1]);
for (int i=0; i<q; ++i) {
if (T[i] > B[i] || L[i] > R[i]) continue;
if (L[i] == 1) F[i] += ps[B[i]] - (T[i] == 1 ? ps[1] : ps[T[i]-1]);
T[i] = max(T[i], 2);
L[i] = max(L[i], 2);
T[i] -= 2, B[i] -= 2, L[i] -= 2, R[i] -= 2;
}
for (int i=0; i<n-2; ++i) {
if (i == 0) mp[0] = (X[2] == 0 && Y[2] == 0 ? 1 : 0);
else if (i == 1) mp[-1] = (Y[3] == 0 && mp[0] == 0 ? 1 : 0), mp[1] = (mp[0] == 0 && X[3] == 0 ? 1 : 0);
else {
auto it = mp.begin();
mp[-i] = (Y[i+2] == 0 && it->second == 0 ? 1 : 0);
it = mp.end();
it = prev(it);
mp[i] = (X[i+2] == 0 && it->second == 0 ? 1 : 0);
}
}
ll k = 0;
for (auto [x, y] : mp) {
V.push_back(y);
mp[x] = k++;
}
ps1.resize(V.size());
ps2.resize(V.size());
ps3.resize(V.size());
rps1.resize(V.size());
for (int j=0; j<V.size(); ++j) {
ps1[j] = V[j] + (j == 0 ? 0 : ps1[j-1]);
ps3[j] = ps1[j] + (j == 0 ? 0 : ps3[j-1]);
}
for (int j=V.size()-1; j>=0; --j) {
rps1[j] = V[j] + (j == V.size()-1 ? 0 : rps1[j+1]);
ps2[j] = rps1[j] + (j == V.size()-1 ? 0 : ps2[j+1]);
}
for (int i=0; i<q; ++i) {
if (T[i] > B[i] || L[i] > R[i]) continue;
F[i] += solve(B[i], R[i]) - (T[i] == 0 ? 0 : solve(T[i]-1, R[i])) - (L[i] == 0 ? 0 : solve(B[i], L[i]-1)) + ((T[i] == 0 || L[i] == 0) ? 0 : solve(T[i]-1, L[i]-1));
}
return F;
}
