#include <bits/stdc++.h> using namespace std; #define ll long long const ll mmod = 998244353; #define vl vector<long long> #define vll vector<vector<long long>> #define pl pair<long long, long long> #define vb vector<bool> 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){ ll n, q; n = X.size(); q = T.size(); vll row3; vll col3; vl x1, y1; for (ll i = 0; i <n; i++){ x1.push_back(X[i]); y1.push_back(Y[i]); } row3.push_back(x1); col3.push_back(y1); row3.push_back({Y[1]}); row3.push_back({Y[2]}); col3.push_back({X[1]}); col3.push_back({X[2]}); for (ll i = 1; i < 3; i++){ for (ll j = 1; j < n; j++){ ll v1 = 0; ll v2 = 0; if (row3[i][j-1] == 0 && row3[i-1][j] == 0){ v1 = 1; } if (col3[i][j-1] == 0 && col3[i-1][j] == 0){ v2 = 1; } row3[i].push_back(v1); col3[i].push_back(v2); } } vl s1, s2, s3; for (ll i = n-1; i>=0; i--){ s1.push_back(col3[0][i]); } for (ll i = 1; i < n; i++){ s1.push_back(row3[0][i]); } for (ll i = n-1; i>=1; i--){ s2.push_back(col3[1][i]); } for (ll i = 2; i < n; i++){ s2.push_back(row3[1][i]); } for (ll i = n-1; i>=2; i--){ s3.push_back(col3[2][i]); } for (ll i = 3; i < n; i++){ s3.push_back(row3[2][i]); } vl p1, p2, p3; p1 = p2 = p3 = {0}; for (ll i = 0; i < s1.size(); i++){ p1.push_back(s1[i] + p1[i]); } for (ll i = 0; i < s2.size(); i++){ p2.push_back(s2[i] + p2[i]); } for (ll i = 0; i < s3.size(); i++){ p3.push_back(s3[i] + p3[i]); } vl q1, q2; q1 = q2 = {0}; for (ll i = 0; i < s3.size(); i++){ q1.push_back(q1[i] + s3[i]*(i+1)); q2.push_back(q2[i] + s3[s3.size()-1-i]*(i+1)); } vl ans; for (ll i = 0; i < q; i++){ ll l, r, u, d; l = L[i]; r = R[i]; u = T[i]; d = B[i]; ll a, b; ll suma = 0; //Layer1 b = 0; a = 1e9; if (l == 0){ a = min(a, n-d-1); b = max(b, n-u); } if (u == 0){ a = min(a, n + l - 1); b = max(b, n + r); } if (a < b){ suma += p1[b] - p1[a]; } //Layer2 b = 0; a = 1e9; if (l <= 1 && r >= 1){ a = min(a, n-d-1); b = max(b, n-max(u,1ll)); } if (u <= 1 && d >= 1){ a = min(a, n + max(l,1ll) - 3); b = max(b, n + r - 2); } if (a < b){ suma += p2[b] - p2[a]; } // Layer3 if (r >= 2 || d >= 2){ l = max(2ll, l); u = max(2ll, u); ll a = l - 2 + (n-1)-d; ll b = r - 2 + n - u; ll t = min(d-u, r-l); // thickness ll v = q2.size(); //arithmetic sequence suma += q1[a+t] - q1[a]; // správně suma += q2[v-b+1] - q2[v-b-t+1]; suma -= (p3[a+t] - p3[a])*a; //správně suma -= (p3[b] - p3[b-t])*(v-b); suma += (p3[b-t] - p3[a+t])*(t+1); //správně } ans.push_back(suma); } return ans; } /*/int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); vector<int> X {0,0,0,0,0,0,0}; vector<int> Y {0,0,0,0,0,0,0}; vector<int> T {2}; vector<int> B {6}; vector<int> L {4}; vector<int> R {6}; vl ans = mosaic(X, Y, T, B, L, R); for (auto x : ans){ cout << x << "\n"; } return 0; } /*/