#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 = X.size(); ll q = T.size(); 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); } } 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 = {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); vl q1 = {0}; for (ll i = 0; i < s3.size(); i++){ q1.push_back(q1.back() + s3[i]*(i+1)); } // q2 SMAZÁNO - není potřeba a způsobuje chyby 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, 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) // Musíme zajistit, že existuje průnik s vnitřní oblastí [2, N-1] ll l_in = max(2ll, l); ll u_in = max(2ll, u); if (l_in <= r && u_in <= d){ // Průnik existuje 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 náběhu (počet kroků - 1) // 1. Rostoucí část (Rising) - Interval [a, a+t] // Oprava indexu: konec je a+t, takže prefix musí být a+t+1 suma += q1[a+t+1] - q1[a]; suma -= (p3[a+t+1] - p3[a]) * a; // 2. Klesající část (Falling) - Interval [b-t, b] // Oprava: Použijeme vzorec místo q2. // Vzorec: (b+2)*SUMA - VAZENA_SUMA ll range_sum = p3[b+1] - p3[b-t]; ll range_w_sum = q1[b+1] - q1[b-t]; suma += range_sum * (b + 2) - range_w_sum; // 3. Plošina (Plateau) - Interval (a+t, b-t) -> indexy [a+t+1, b-t-1] // Pokud se intervaly nepřekrývají (b-t > a+t) if (b - t > a + t) { // Oprava indexů: od konce rostoucí (a+t+1) do začátku klesající (b-t) suma += (p3[b-t] - p3[a+t+1]) * (t + 1); } else { // Specialita: Pokud je obdélník tak malý, že se náběh a pokles překrývají, // musíme odečíst dvojí započtení středu. // Ale pro t = min(h, w) se v "trapezoid" logice nepřekrývají, // jen se dotýkají nebo splynou do trojúhelníku (plošina délky 0). // Logika výše to zvládne (p3[X] - p3[Y] kde X <= Y dá 0). } } ans.push_back(suma); } return ans; }