#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long int
#define cerr if(0) cerr
const int N = 2e5+100;
ll T[4*N], sum[4*N], TT[4*N];
int sz[4*N];
void build(int l, int r, int k){
if(l == r){
T[k] = 0;
TT[k] = 0;
sum[k] = 0;
sz[k] = 1;
}else{
int mid = l+r>>1;
build(l, mid, k<<1);
build(mid+1, r, k<<1|1);
TT[k] = 0;
T[k] = 0;
sum[k] = 0;
sz[k] = sz[k<<1] + sz[k<<1|1];
}
}
void upd(int l, int r, int p, int k, int val){
if(l == r){
T[k] = val;
TT[k] = val;
sum[k] = val;
sz[k] = 1;
return;
}
int mid = l+r>>1;
if(p <= mid) upd(l, mid, p, k<<1, val);
else upd(mid+1, r, p, k<<1|1, val);
T[k] = T[k<<1|1] + T[k<<1] + sz[k<<1|1] * sum[k<<1];
TT[k] = TT[k<<1|1] + TT[k<<1] + sz[k<<1] * sum[k<<1|1];
sum[k] = sum[k<<1] + sum[k<<1|1];
sz[k] = sz[k<<1] + sz[k<<1|1];
}
array<ll, 3> get(int l, int r, int ql, int qr, int k){
if(ql > r || l > qr) return array<ll, 3>{0, 0, 0};
if(ql <= l && r <= qr){
return {T[k], sum[k], sz[k]};
}
int mid = l+r>>1;
array<ll, 3> p = get(l, mid, ql, qr, k<<1);
array<ll, 3> q = get(mid+1, r, ql, qr, k<<1|1);
if(q[2] == 0) return p;
if(p[2] == 0) return q;
array<ll, 3> res;
res[1] = q[1] + p[1];
res[0] = q[0] + p[0] + p[1] * q[2];
res[2] = q[2] + p[2];
return res;
}
array<ll, 3> get2(int l, int r, int ql, int qr, int k){
if(ql > r || l > qr) return array<ll, 3>{0, 0, 0};
if(ql <= l && r <= qr){
return {TT[k], sum[k], sz[k]};
}
int mid = l+r>>1;
array<ll, 3> p = get2(l, mid, ql, qr, k<<1);
array<ll, 3> q = get2(mid+1, r, ql, qr, k<<1|1);
if(q[2] == 0) return p;
if(p[2] == 0) return q;
array<ll, 3> res;
res[1] = q[1] + p[1];
res[0] = q[0] + p[0] + q[1] * p[2];
res[2] = q[2] + p[2];
return res;
}
ll get3(int l, int r, int ql, int qr, int k){
if(ql > r || l > qr) return 0ll;
if(ql <= l && r <= qr) return sum[k];
int mid = l+r>>1;
return get3(l, mid, ql, qr, k<<1) + get3(mid+1, r, ql, qr, k<<1|1);
}
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) {
int n = X.size();
int q = T.size();
build(1, n * 2, 1);
vector<vector<pii>> qp(q);
vector<array<int, 3>> Q;
int id = 0;
function<int(int, int)> add_q = [&](int l, int r){
Q.pb({l, r, id});
++id;
return id-1;
};
if(n == 1){
vector<ll> C(q, X[0]);
return C;
}
vector<ll> ANS(id);
vector<ll> prefX(n);
vector<ll> prefY(n);
prefX[0] = X[0];
prefY[0] = Y[0];
for(int i = 1; i < n; ++i) prefX[i] = prefX[i - 1] + X[i];
for(int i = 1; i < n; ++i) prefY[i] = prefY[i - 1] + Y[i];
vector<ll> F;
for(int i = 0; i < q; ++i){
int x1 = T[i], x2 = B[i];
int y1 = L[i], y2 = R[i];
F.pb(prefX[y2] - (y1 == 0 ? 0ll : prefX[y1 - 1]));
qp[i].pb({add_q(x2, y2), 1});
if(y1 > 0)
qp[i].pb({add_q(x2, y1 - 1), -1});
if(x1 > 0)
qp[i].pb({add_q(x1 - 1, y2), -1});
if(y1 > 0 && x1 > 0)
qp[i].pb({add_q(x1 - 1, y1 - 1), 1});
}
return F;
vi D;
int last = Y[1];
for(int i = 1; i < n; ++i){
if(last == 0 && X[i] == 0) D.pb(1);
else D.pb(0);
last = D.back();
}
reverse(all(D));
last = D.back();
for(int i = 2; i < n; ++i){
if(last == 0 && Y[i] == 0) D.pb(1);
else D.pb(0);
last = D.back();
}
// id from 1 to 2*n-3
for(int i = 1; i <= 2*n-3; ++i){
upd(1, 2*n, i, 1, D[i-1]);
cerr << D[i-1] << ' ';
}
cerr <<" arran\n\n\n";
// for(int x: D) cerr << x << ' ';
// return vector<ll>(q, 0);
int sz = 2*n;
int p = 0;
for(auto [x, y, ID]: Q){
if(x == 0){
ANS[ID] = prefX[y];
}else if(y == 0){
ANS[ID] = prefY[x];
}else{
ANS[ID] = prefX[y] + prefY[x] - X[0];
// + something from the segtree...
int row_id = n-1 + x-1;
int col_id = n-1-y+1;
int origin = n-1;
if(x == y){
// cerr << row_id << ' ' << col_id << " pf\n";
// cerr << get2(1, sz, origin, row_id, 1)[1] << ' ' << get2(1, sz, origin, row_id, 1)[2] << " f\n";
ANS[ID] += get(1, sz, origin, row_id, 1)[0];
ANS[ID] += get2(1, sz, col_id, origin - 1, 1)[0];
}else{
int mn = min(x, y);
ANS[ID] += get(1, sz, row_id - mn + 1, row_id, 1)[0];
ANS[ID] += get2(1, sz, col_id, col_id + mn - 1, 1)[0];
ANS[ID] += get3(1, sz, col_id + mn, row_id - mn, 1) * mn;
}
}
}
vector<ll> C(q);
for(int i = 0; i < q; ++i){
for(auto [ID, p]: qp[i]){
C[i] += ANS[ID] * p;
cerr << ID << ' ' << ANS[ID] << " crap\n";
}
cerr << '\n';
}
return C;
}
