#include "mosaic.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <vector>
#include <iostream>
using namespace std;
int lin[3][200005];
int col[3][200005];
int spar[3][200005];
int spar2[3][200005];
int coefdiag[400005];
int nmax=200000;
long long diag(int i,int j)
{
if(i<0 || j<0)
{
return 0;
}
int a=nmax-i;
int b=min(nmax,nmax+j-i);
int c=max(nmax,nmax+j-i);
int d=nmax+j;
long long sum=0,coef=1;
for(int i=a; i<b; i++)
{
sum+=coefdiag[i]*coef;
coef++;
}
for(int i=b; i<=c; i++)
{
sum+=coefdiag[i]*coef;
}
for(int i=c+1; i<=d; i++)
{
coef--;
sum+=coefdiag[i]*coef;
}
return sum;
}
long long solve(int i,int j)
{
if(i<0 || j<0)
{
return 0;
}
long long sum=0;
if(i>=1 && j>=1)
{
sum=spar[0][j]+spar[1][j]+spar2[0][i]+spar2[1][i]-spar[0][1]-spar[1][1];
}
else if(i>=1)
{
sum=spar2[0][i];
}
else if(j>=1)
{
sum=spar[0][j];
}
else
{
sum=spar[0][0];
}
return sum+diag(i-2,j-2);
}
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 Q=L.size();
std::vector<long long> C(Q, 0);
int n=X.size();
for(int i=0; i<n; i++)
{
lin[0][i]=X[i];
}
for(int i=0; i<n; i++)
{
col[0][i]=Y[i];
}
for(int i=1; i<=2; i++)
{
lin[i][0]=col[0][i];
//cout<<"lin"<<" "<<i<<"\n";
for(int j=1; j<n; j++)
{
lin[i][j]=1^(lin[i-1][j]|lin[i][j-1]);
//cout<<lin[i][j]<<" ";
}
//cout<<'\n';
}
for(int i=1; i<=2; i++)
{
col[i][0]=lin[0][i];
// cout<<"col"<<" "<<i<<"\n";
for(int j=1; j<n; j++)
{
col[i][j]=1^(col[i-1][j]|col[i][j-1]);
//cout<<col[i][j]<<" ";
}
//cout<<'\n';
}
for(int i=0; i<=1; i++)
{
spar[i][0]=lin[i][0];
spar2[i][0]=col[i][0];
for(int j=1; j<n; j++)
{
spar[i][j]=spar[i][j-1]+lin[i][j];
spar2[i][j]=spar2[i][j-1]+col[i][j];
}
}
for(int j=2; j<n; j++)
{
coefdiag[j+nmax-2]=lin[2][j];
}
for(int j=2; j<n; j++)
{
coefdiag[nmax-j+2]=col[2][j];
}
for(int i=0; i<Q; i++)
{
long long rez=0;
rez=solve(B[i],R[i])-solve(B[i],L[i]-1)-solve(T[i]-1,R[i])+solve(T[i]-1,L[i]-1);
C[i]=rez;
}
return C;
}
