#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>> 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 = X.size(); ll q = T.size(); // --- Příprava mřížky (beze změny) --- vll row3, 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); } } // --- Linearizace (beze změny) --- 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]); // --- Prefixové součty --- vl p1 = {0}, p2 = {0}, p3 = {0}; for (ll x : s1) p1.push_back(p1.back() + x); for (ll x : s2) p2.push_back(p2.back() + x); for (ll x : s3) p3.push_back(p3.back() + x); // Vážený prefix pro Layer 3: q1[i] = suma s3[k]*(k+1) vl q1 = {0}; for (ll i = 0; i < s3.size(); i++){ q1.push_back(q1.back() + s3[i] * (i + 1)); } vl ans; for (ll i = 0; i < q; i++){ ll l = L[i], r = R[i], u = T[i], d = B[i]; ll a, b; ll suma = 0; // --- Layer 1 --- 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]; // --- Layer 2 --- 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]; // --- Layer 3 (OPRAVENO) --- if (r >= 2 && d >= 2){ ll l_in = max(2ll, (ll)l); ll u_in = max(2ll, (ll)u); // Kontrola existence obdélníku if (l_in < r && u_in < d) { ll a = l_in - 2 + (n - 1) - d; ll b = r - 2 + n - u_in; ll t = min(d - u_in, r - l_in); // Tloušťka // Klíčové: Bod zlomu (index, kde končí polovina intervalu) ll mid = (a + b - 1) / 2; // Definice hranic (Rising / Falling) ll end_rise = min(mid, a + t - 1); ll start_fall = max(mid + 1, b - t + 1); // 1. Růst (Rising) if (a <= end_rise) { suma += (q1[end_rise + 1] - q1[a]); suma -= (p3[end_rise + 1] - p3[a]) * a; } // 2. Pokles (Falling) if (start_fall <= b) { ll range_sum = p3[b + 1] - p3[start_fall]; ll range_w_sum = q1[b + 1] - q1[start_fall]; // ZDE BYLA CHYBA: Musí být (b + 2), aby seděl vzorec (b - i + 1) suma += range_sum * (b + 2) - range_w_sum; } // 3. Plošina (Plateau) if (end_rise + 1 < start_fall) { suma += (p3[start_fall] - p3[end_rise + 1]) * t; } } } ans.push_back(suma); } return ans; }