#include "mosaic.h" #include <bits/stdc++.h> using namespace std; bool BEGIN_ALLOC; #define FOR(i, l, r) for(int i = (l); i < (r); ++i) #define F0R(i, r) FOR(i, 0, r) #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) #define sz(v) (int)v.size() #define pb push_back #define eb emplace_back #define ff first #define ss second #define mp make_pair #define mt make_tuple #define tcT template<class T tcT> bool minimize(T& a, const T& b){ return (a > b ? a = b, 1 : 0); } tcT> bool maximize(T& a, const T& b){ return (a < b ? a = b, 1 : 0); } using ll = long long; using db = double; using ull = unsigned long long; using pi = pair<int, int>; using pl = pair<ll, ll>; using vi = vector<int>; using vl = vector<ll>; using vpi = vector<pi>; using vpl = vector<pl>; std::vector<long long> mosaic124(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> L, std::vector<int> R) { int N = sz(X), Q = sz(T); vector<vi> pref(N, vi(N)), a(N, vi(N)); F0R(i, N){ pref[0][i] = a[0][i] = X[i]; pref[i][0] = a[i][0] = Y[i]; } F0R(i, N){ F0R(j, N){ if(i > 0 && j > 0){ a[i][j] = (a[i - 1][j] == 0 && a[i][j - 1] == 0 ? 1 : 0); } pref[i][j] = a[i][j]; if(i > 0) pref[i][j] += pref[i - 1][j]; if(j > 0) pref[i][j] += pref[i][j - 1]; if(i > 0 && j > 0) { pref[i][j] -= pref[i - 1][j - 1]; } } } auto sumRect = [&](int a, int b, int c, int d){ return pref[c][d] - (b == 0 ? 0 : pref[c][b - 1]) - (a == 0 ? 0 : pref[a - 1][d]) + (a == 0 || b == 0 ? 0 : pref[a - 1][b - 1]); }; vl ans(Q); F0R(i, Q){ ans[i] = sumRect(T[i], L[i], B[i], R[i]); } return ans; } std::vector<long long> mosaic6(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> L, std::vector<int> R) { int N = sz(X), Q = sz(T); vector<vi> a(N), pref(N); F0R(i, N){ if(i < 3){ a[i].resize(N); } else{ a[i].resize(3); } if(i == 0) a[i] = X; a[i][0] = Y[i]; if(i > 0){ FOR(j, 1, sz(a[i])){ a[i][j] = (a[i - 1][j] == 0 && a[i][j - 1] == 0); } } // F0R(j, sz(a[i])){ // pref[i][j] = a[i][j]; // if(i > 0) pref[i][j] += pref[i - 1][j]; // if(j > 0) pref[i][j] += pref[i][j - 1]; // if(i > 0 && j > 0) pref[i][j] -= pref[i - 1][j - 1]; // } } // cerr << "preprocess ! \n"; auto querySingle = [&](int x, int y){ // cerr << "wtf " << x << ' ' << y << '\n'; if(min(x, y) < 3){ return a[x][y]; } if(x <= y){ int ret = x - 2; // cerr << x - ret << ' ' << y - ret << " !\n"; return a[x - ret][y - ret]; } else{ int ret = y - 2; return a[x - ret][y - ret]; } }; vl ans(Q); auto query = [&](int a, int b, int c, int d){ if(a == c && b == d) return querySingle(a, b); return 0; }; F0R(i, Q){ ans[i] = query(T[i], L[i], B[i], R[i]); } return ans; } 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) { if(sz(X) <= 5000) return mosaic124(X, Y, T, B, L, R); if(L == R && T == B) return mosaic6(X, Y, T, B, L, R); int N = sz(X), Q = sz(T); vector<vi> a(N), pref(N); F0R(i, N){ if(i < 3){ a[i].resize(N); pref[i].resize(N); } else{ a[i].resize(3); pref[i].resize(3); } if(i == 0) a[i] = X; a[i][0] = Y[i]; if(i > 0){ FOR(j, 1, sz(a[i])){ a[i][j] = (a[i - 1][j] == 0 && a[i][j - 1] == 0); } } F0R(j, sz(a[i])){ pref[i][j] = a[i][j]; if(i > 0) pref[i][j] += pref[i - 1][j]; if(j > 0) pref[i][j] += pref[i][j - 1]; if(i > 0 && j > 0) pref[i][j] -= pref[i - 1][j - 1]; } } auto querySingle = [&](int x, int y){ // cerr << "wtf " << x << ' ' << y << '\n'; if(min(x, y) < 3){ return a[x][y]; } if(x <= y){ int ret = x - 2; // cerr << x - ret << ' ' << y - ret << " !\n"; return a[x - ret][y - ret]; } else{ int ret = y - 2; return a[x - ret][y - ret]; } }; vl ans(Q); vl row2, col2; FOR(i, 2, N) { row2.pb(a[2][i]); col2.pb(a[i][2]); } vl sumRow(sz(row2)), sumCol(sz(col2)); vl sumRowMul(sz(row2)), sumColMul(sz(col2)); F0R(i, sz(row2)){ sumRow[i] = (i > 0 ? sumRow[i - 1] : 0) + row2[i]; sumCol[i] = (i > 0 ? sumCol[i - 1] : 0) + col2[i]; sumRowMul[i] = (i > 0 ? sumRowMul[i - 1] : 0) + row2[i] * i; sumColMul[i] = (i > 0 ? sumColMul[i - 1] : 0) + col2[i] * i; } auto sumRev = [&](vl& sum, vl& sumMul, int n){ return (n + 1) * sum[n] - sumMul[n]; }; function<ll(int, int)> solveUpperTriangle = [&](int n, int m){ if(n == m) return sumRev(sumRow, sumRowMul, n); if(n <= m){ ll ans = sumRev(sumRow, sumRowMul, m); ans -= solveUpperTriangle(m - n - 1, m - n - 1); return ans; } else{ ll ans = sumRev(sumRow, sumRowMul, m); return ans; } }; function<ll(int, int)> solveLowerTriangle = [&](int n, int m){ if(n == m) return sumRev(sumCol, sumColMul, n); if(n <= m){ return sumRev(sumCol, sumColMul, n); } else{ ll ans = sumRev(sumCol, sumColMul, n); ans -= solveLowerTriangle(n - m - 1, n - m - 1); return ans; } }; auto solveRect = [&](int n, int m){ if(n < 0 || m < 0) return 0ll; if(min(n, m) < 3) return 1LL * pref[n][m]; ll partL = pref[1][m] + pref[n][1] - pref[1][1]; ll partU = solveUpperTriangle(n - 2, m - 2); ll partD = solveLowerTriangle(n - 2, m - 2); ll diag = min(n - 1, m - 1) * a[2][2]; return partL + partU + partD - diag; }; auto query = [&](int a, int b, int c, int d){ ll v1 = solveRect(c, d); ll v2 = solveRect(a - 1, d); ll v3 = solveRect(c, b - 1); ll v4 = solveRect(a - 1, b - 1); return v1 - v2 - v3 + v4; }; F0R(i, Q){ ans[i] = query(T[i], L[i], B[i], R[i]); } return ans; } #ifdef LOCAL int main(){ freopen("task.inp", "r", stdin); freopen("task.out", "w", stdout); int N; cin >> N; vi X(N), Y(N); F0R(i, N) cin >> X[i]; F0R(i, N) cin >> Y[i]; int Q; cin >> Q; vi T(Q), B(Q), L(Q), R(Q); F0R(i, Q){ cin >> T[i] >> B[i] >> L[i] >> R[i]; } vl ans = mosaic(X, Y, T, B, L, R); for(auto x : ans) cout << x << ' '; return 0; } #endif //LOCAl