#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> fenwick(5e5, 0);
void add(int n, int pos) {
while (pos <= n) {
++fenwick[pos];
pos += (pos)&(-pos);
}
}
ll get(int n, int pos) {
ll res = 0;
while (pos >= 1) {
res += fenwick[pos];
pos -= (pos)&(-pos);
}
return res;
}
ll sum(int n, int left, int right) {
return get(n, right) - (left > 1 ? get(n, left - 1) : 0);
}
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 = (int)T.size();
std::vector<long long> C(Q, 0);
int n = X.size();
if (n == 1) return vector<ll>(Q, X[0]);
vector<vector<pair<int, pair<int, int>>>> queries(n);
for (int i = 0; i < Q; ++i) queries[T[i]].push_back({i, {L[i], R[i]}});
vector<ll> preSum0(n, X[0]);
for (int i = 1; i < n; ++i) preSum0[i] = preSum0[i - 1] + X[i];
for (auto &[idx, lAndr] : queries[0]) C[idx] = preSum0[lAndr.second] - (lAndr.first ? preSum0[lAndr.first - 1] : 0);
vector<int> row1(n), col1(n), col2(n);
row1[0] = Y[1]; col1[0] = X[1];
for (int i = 1; i < n; ++i) row1[i] = ((row1[i - 1] + X[i] == 0) ? 1 : 0), col1[i] = ((col1[i - 1] + Y[i] == 0) ? 1 : 0);
if (n > 2) {
col2[0] = X[2];
for (int i = 1; i < n; ++i) col2[i] = ((col2[i - 1] + col1[i] == 0) ? 1 : 0);
}
int curShift = n + 5, fenwickN = curShift * 2;
for (int i = 1; i < n; ++i) {
if (row1[i]) add(fenwickN, curShift + i);
}
for (int i = 1; i < n; ++i) {
// cout << "I: " << i << endl;
// for (int j = 1; j <= fenwickN; ++j) cout << sum(fenwickN, j, j) << ' ';
// cout << endl;
for (auto &[idx, lAndr] : queries[i]) C[idx] = sum(fenwickN, lAndr.first + curShift, lAndr.second + curShift) + (lAndr.first == 0 ? Y[i] : 0);
--curShift;
if (i < n - 1 && col1[i + 1]) {
add(fenwickN, curShift + 1);
}
if (i != 1 && i < n - 1 && col2[i + 1] && col1[i] == 0) add(fenwickN, curShift + 2);
if (i == 1 && i < n - 1) {
int prev = col1[i + 1];
for (int j = 2; j < n; ++j) {
if (row1[j - 1] + row1[j] + prev == 0) add(fenwickN, curShift + j);
if (row1[j] + prev == 0) prev = 1;
else prev = 0;
}
}
// for (int j = 1; j <= fenwickN; ++j) cout << sum(fenwickN, j, j) << ' ';
// cout << endl;
}
return C;
}
