#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> // Funkce mosaic 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(); // 1. Příprava mřížky (tvůj původní kód) 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); } } // 2. Linearizace do s1, s2, s3 (tvůj původní kód) 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]); } // 3. Prefixové součty // Změna: p1, p2, p3 inicializujeme s {0}, aby p[i] byl součet prvních i prvků 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ý prefixový součet pro Layer 3 (místo q2) vl q1 = {0}; for (ll i = 0; i < s3.size(); i++){ q1.push_back(q1.back() + s3[i] * (i + 1)); } // q2 jsme smazali, není potřeba 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 (OPRAVENO) --- // Podmínka && je nutná, jinak saháme mimo pole s3 if (r >= 2 && d >= 2){ ll l_in = max(2ll, (ll)l); ll u_in = max(2ll, (ll)u); // Ověříme, zda oříznutý obdélník dává smysl 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 // Metoda středu (řeší překryvy trojúhelníků) ll mid = (a + b) / 2; ll end_rise = min(a + t, mid); // Konec náběhu ll start_fall = max(b - t, mid + 1); // Začátek poklesu // 1. Rostoucí část (Rising) // Váha roste: s3[k] * (k - a + 1) // Suma = (q1[R] - q1[L]) - a * (p3[R] - p3[L]) if (a <= end_rise) { suma += (q1[end_rise + 1] - q1[a]); suma -= (p3[end_rise + 1] - p3[a]) * a; } // 2. Klesající část (Falling) // Váha klesá: s3[k] * (b - k + 1) -> (b+2 - (k+1)) // Suma = (b+2)*(p3[R] - p3[L]) - (q1[R] - q1[L]) if (start_fall <= b) { ll range_sum = p3[b + 1] - p3[start_fall]; ll range_w_sum = q1[b + 1] - q1[start_fall]; suma += range_sum * (b + 2) - range_w_sum; } // 3. Plošina (Plateau) // Váha je konstantní: t + 1 if (end_rise + 1 < start_fall) { suma += (p3[start_fall] - p3[end_rise + 1]) * (t + 1); } } } ans.push_back(suma); } return ans; }