#include "bits/stdc++.h"
#define ll long long
#define pb push_back
#define pii pair<int, int>
using namespace std;
const int N = 4e5+5;
int cnt[N], arcalyk[4][N], tarhun[N][4];
const int M = 5005;
int dp[M][M];
int wow(int a, int b){
return (!(a|b)?1:0);
}
vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){
int n = (int)X.size();
assert(X.front()==Y.front());
if (n <= 5000){
for (int i = 0; i < n; i++)
dp[1][i+1] = X[i];
for (int i = 0; i < n; i++)
dp[i+1][1] = Y[i];
for (int i = 2; i <= n; i++)
for (int j = 2; j <= n; j++)
dp[i][j] = wow(dp[i-1][j], dp[i][j-1]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
vector<ll> ans;
for(int i = 0; i < (int)L.size(); ++i){
int x = T[i]+1, y = L[i]+1, yy = R[i]+1, xx = B[i]+1;
ans.push_back(dp[xx][yy] - dp[x-1][yy] - dp[xx][y-1] + dp[x-1][y-1]);
}
return ans;
}
bool ok = true;
for (int i = 0; i < n; i++)
ok &= X[i] == 0, ok &= Y[i] == 0;
if (ok){
vector<ll> ans;
for(int i = 0; i < (int)L.size(); ++i){
int x = T[i]+1, y = L[i]+1, yy = R[i]+1, xx = B[i]+1;
if (x == 1)
x += 1;
if (y == 1)
y += 1;
ll rec = (xx-x+1)*1LL*(yy-y+1);
if (rec % 2 == 0)
ans.push_back(rec/2);
else{
if ((xx+yy)%2)
ans.push_back(rec/2);
else
ans.push_back(rec/2+1);
}
}
return ans;
}
map<pii, int> mp;
for(int i = 1; i <= n; ++i)
mp[{1, i}] = X[i-1], mp[{i, 1}] = Y[i-1];
for(int i = 2; i <= n; ++i)
for(int j = 2; j <= 3; ++j)
mp[{i, j}] = wow(mp[{i-1, j}], mp[{i, j-1}]);
for(int i = 2; i <= 3; ++i)
for(int j = 2; j <= n; ++j)
mp[{i, j}] = wow(mp[{i-1, j}], mp[{i, j-1}]);
// int ii = 3;
// for(int jj = 3; jj <= n; ++jj)
// cnt[ii-jj+n] = mp[{ii, jj}];
for (auto [key, value]: mp)
cnt[key.first-key.second+n] = value;
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= n; j++)
arcalyk[i][j] = mp[{i,j}] + arcalyk[i][j-1];
for (int j = 1; j <= 3; j++)
for (int i = 1; i <= n; i++)
tarhun[i][j] = mp[{i,j}] + tarhun[i-1][j];
// for (int i = 1; i < n+n; i++)
// cnt[i] += cnt[i-1];
vector<ll> ans;
for(int i = 0; i < (int)L.size(); ++i){
int x = T[i]+1, y = L[i]+1, yy = R[i]+1, xx = B[i]+1;
ll res = 0;
while (x <= 3 and x <= xx)
res += arcalyk[x][yy]-arcalyk[x][y-1], x += 1;
if (x <= xx){
while (y <= 3 and y <= yy)
res += tarhun[xx][y]-tarhun[x-1][y], y += 1;
}
if (x <= xx and y <= yy){
int a = x-y+n, b = x-yy+n, k = xx-x+1;
swap(a, b);
b += k-1;
for (int j = 0; j < k; j++){
res += cnt[a++] * 1LL * (j+1);
if (a <= b)
res += cnt[b--] * 1LL * (j+1);
}
res += (b-a+1)*1LL*k;
// for (int i = 0; i <= ; i++){
// res += cnt[a] - cnt[b-1];
// a += 1;
// b += 1;
// }
}
ans.pb(res);
}
return ans;
}
l = 1, r = 2, k = 5
1 2 3 4 5 6 7 8
1 1
1 1
1 1
1 1
1 1
1 2 2 2 2 1
int main(){
int n;
scanf("%d", &n);
vector<int> X, Y;
for(int i = 1; i <= n; ++i){
int x;
scanf("%d", &x);
X.pb(x);
}
for(int i = 1; i <= n; ++i){
int x;
scanf("%d", &x);
Y.pb(x);
}
int q;
scanf("%d", &q);
vector<int> T, B, L, R;
while(q--){
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
T.pb(a), B.pb(b), L.pb(c), R.pb(d);
}
vector<ll> ans = mosaic(X, Y, T, B, L, R);
for(ll i : ans)
printf("%lld ", i);
puts("");
return 0;
}
Compilation message
mosaic.cpp:111:1: error: 'l' does not name a type
111 | l = 1, r = 2, k = 5
| ^
