#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]); } // Prefixové součty inicializujeme s nulou na začátku 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] = součet s3[k]*(k+1) pro k < i 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, r, u, d; 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 (FINÁLNÍ OPRAVA) --- if (r >= 2 && d >= 2){ ll l_in = max(2ll, (ll)l); ll u_in = max(2ll, (ll)u); // Musíme zkontrolovat, zda po oříznutí zbyl platný obdélník if (l_in < r && u_in < d) { // Pozor: r a d jsou exclusive hranice ll a = l_in - 2 + (n - 1) - d; ll b = r - 2 + n - u_in; // 'a' je inclusive start, 'b' je exclusive end (velikost intervalu = b - a) ll t = min(d - u_in, r - l_in); // Skutečná tloušťka v Layer 3 // Bod zlomu (vrchol trojúhelníku) // (a + b - 1) / 2 zajistí správné rozdělení i pro sudé/liché délky ll mid = (a + b - 1) / 2; // Definice hranic: // Růst končí buď v půlce (trojúhelník), nebo když dosáhne tloušťky t (lichoběžník) // Indexy jsou inkluzivní pro výpočet end_rise ll end_rise = min(mid, a + t - 1); // Pokles začíná za půlkou, nebo když se tloušťka začne zmenšovat z t ll start_fall = max(mid + 1, b - t); // 1. Část RŮST [a, end_rise] if (a <= end_rise) { // Interval [a, end_rise + 1) v prefixech suma += (q1[end_rise + 1] - q1[a]); suma -= (p3[end_rise + 1] - p3[a]) * a; } // 2. Část POKLES [start_fall, b) if (start_fall < b) { // Interval [start_fall, b) v prefixech // Váha klesá jako: b - index // Vzorec: (b+1)*Suma - VáženáSuma ll range_sum = p3[b] - p3[start_fall]; ll range_w_sum = q1[b] - q1[start_fall]; suma += range_sum * (b + 1) - range_w_sum; } // 3. Část PLOŠINA (mezi nimi) if (end_rise + 1 < start_fall) { suma += (p3[start_fall] - p3[end_rise + 1]) * t; } } } ans.push_back(suma); } return ans; }