#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
struct segTree{
long long *st;
int n;
segTree(int siz){
int x= ceil(log2(siz));
x++;
n=siz-1;
st=new long long[(1<<x)];
fill(st,st+(1<<x),0);
}
void rupdate(int l, int r, int ind, int i, int val){
if(i<l||i>r)
return;
if(l==r){
st[ind]=val;
return;
}
int mid = (l+r)/2;
rupdate(l,mid,ind*2+1,i,val);
rupdate(mid+1,r,ind*2+2,i,val);
st[ind]=st[ind*2+1]+st[ind*2+2];
}
void update(int i, int val){
rupdate(0,n,0,i,val);
}
long long rquery(int l, int r, int s, int e, int ind){
if(e<l||s>r)
return 0;
if(s<=l&&r<=e){
return st[ind];
}
int mid = (l+r)/2;
return rquery(l,mid,s,e,ind*2+1)+rquery(mid+1,r,s,e,ind*2+2);
}
long long query(int l, int r){
return rquery(0,n,l,r,0);
}
};
vector<long long> mosaic(vector<int> X, vector<int> Y,vector<int> T, vector<int> B,vector<int> L, vector<int> R) {
int n = X.size();
int q = (int)T.size();
if(n==1){
vector<long long>ans(q,X[0]);
return ans;
}
else if(n==2){
int rem = 0;
if(X[1]==Y[1]&&X[1]==0){
rem=1;
}
vector<long long>ans(q);
for(int i = 0;i<q;i++){
//later
if(T[i]==0){
if(L[i]==0){
ans[i]+=X[0];
}
if(R[i]==1){
ans[i]+=X[1];
}
}
if(B[i]==1){
if(L[i]==0){
ans[i]+=Y[1];
}
if(R[i]==1){
ans[i]+=rem;
}
}
}
return ans;
}
//X is row top
vector<long long>nxc1(n-1);
vector<long long>nxc2(n-2);
vector<long long>nxr1(n-1);
vector<long long>nxr2(n-2);
nxc1[0]=nxr1[0]=((bool)(X[1]==0&&Y[1]==0));
for(int i = 1;i<n-1;i++){
nxc1[i]=(nxc1[i-1]==0&&Y[i+1]==0);
nxr1[i]=(nxr1[i-1]==0&&X[i+1]==0);
}
nxc2[0]=nxr2[0]=((bool)(nxc1[1]==0&&nxr1[1]==0));
for(int i = 1;i<n-2;i++){
nxc2[i]=(nxc2[i-1]==0&&nxc1[i+1]==0);
nxr2[i]=(nxr2[i-1]==0&&nxr1[i+1]==0);
}
int off = n+5;
segTree up(3*n);
segTree flat(3*n);
segTree down(3*n);
for(int i = 0;i<n-2;i++){
if(nxc1[i]){
int k = 2-(2+i);
int offd = k+off;
//cout << "adding1: " << k << "\n";
//cout << "offd: " << offd << "\n";
up.update(offd,offd);
flat.update(offd,1);
down.update(offd,-offd);
}
if(nxr1[i]){
int k = (i+2)-2;
int offd = k+off;
//cout << "adding2: " << k << "\n";
//cout << "offd: " << offd << "\n";
up.update(offd,offd);
flat.update(offd,1);
down.update(offd,-offd);
}
}
for(int i = 1;i<n;i++){
X[i]+=X[i-1];
Y[i]+=Y[i-1];
}
for(int i = 1;i<n-1;i++){
nxc1[i]+=nxc1[i-1];
nxr1[i]+=nxr1[i-1];
}
for(int i = 1;i<n-2;i++){
nxc2[i]+=nxc2[i-1];
nxr2[i]+=nxr2[i-1];
}
//segs made
vector<long long>ans(q);
for(int i = 0;i<q;i++){
long long curr=0;
int t,bo,l,r;
bo=T[i];
t=B[i];
l=L[i];
r=R[i];
int a = max(2,l)-t+off;
int b = max(2,l)-max(2,bo)+off;
int c = r-t+off;
int d = r-max(2,bo)+off;
//cout << a << " " << b << " " << c << " " << d << "\n";
curr+=up.query(a,b)-flat.query(a,b)*(a-1);
curr+=flat.query(b+1,c)*(min(r-l+1,t-b+1));
curr+=-down.query(c+1,d)-(1LL*(c)*flat.query(c+1,d));
//cout << "segs: " << curr << "\n";
if(bo<2){
if(r-1>=0)
curr+=nxr1[r-1];
if(l-2>=0)
curr-=nxr1[l-2];
if(bo<1){
if(r>=0)
curr+=X[r];
if(l-1>=0)
curr-=X[l-1];
}
}
//cout << "part1: " << curr << "\n";
if(l<2){
if(t-1>=0){
curr+=nxc1[t-1];
curr-=nxc1[max(0,bo-2)];
}
//cout << "part2.1: " << curr << "\n";
if(l<1){
if(t>=0){
curr+=Y[t];
curr-=Y[max(0,bo-1)];
}
}
}
//cout << bo << " " << t << " " << l << " " << r << " " << curr << "\n";
ans[i]=curr;
}
return ans;
}
