Editorial for Bedao Regular Contest 06 - REWARDS
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Gọi ~S_{xyzt}~ là tổng của các ~a_{x'y'z't'}~ với ~1 \leq x' \leq x~; ~ 1 \leq y' \leq y~ ; ~ 1 \leq z' \leq z~ ; ~1 \leq t' \leq t~. Sau đó ~S_{xyzt}~ được tính bằng bao hàm loại trừ như sau:
s[x][y][z][t] = a[x][y][z][t];
for (int mask = 1; mask < 16; mask++) {
int nx = x - ((mask & 1) > 0);
int ny = y - ((mask & 2) > 0);
int nz = z - ((mask & 4) > 0);
int nt = t - ((mask & 8) > 0);
if (((nx != x) + (ny != y) + (nz != z) + (nt != t)) % 2)
s[x][y][z][t] += s[nx][ny][nz][nt];
else
s[x][y][z][t] -= s[nx][ny][nz][nt];
}
Ta sẽ tính ~S_{xyzt}~ đựa vào các ~S_{x | x-1, y | y-1, z | z-1, t | t-1}~ thì Bit thứ ~i~ (~0~, ~1~, ~2~ hoặc ~3~) của mask sẽ đại diện cho việc ta lấy ~x~ hay ~x-1~, ~y~ hay ~y-1~, ~\dots~ Theo nguyên lí bù trừ, nếu số Bit là lẻ thì ta cộng ~S~ đó vào ~S_{xyzt}~ ngược lại ta trừ ~S_{xyzt}~ cho ~S~ đó.
Để tính truy vấn, ta cũng sử dụng nguyên lí tương tự, nhưng ta sẽ chọn ~x_2~ nếu Bit thứ ~0~ bằng ~0~ và ~x_{1}-1~ nếu Bit thứ ~0~ bằng ~1~, tương tự với ~y~, ~z~ và ~t~
ll getSum(int x, int y, int z, int t, int xx, int yy, int zz, int tt) {
ll ans = s[xx][yy][zz][tt];
for (int mask = 1; mask < 16; mask++) {
int nx = (mask & 1) > 0 ? x - 1 : xx;
int ny = (mask & 2) > 0 ? y - 1 : yy;
int nz = (mask & 4) > 0 ? z - 1 : zz;
int nt = (mask & 8) > 0 ? t - 1 : tt;
if (((nx != xx) + (ny != yy) + (nz != zz) + (nt != tt)) % 2)
ans -= s[nx][ny][nz][nt];
else
ans += s[nx][ny][nz][nt];
}
return ans;
}
Code mẫu
#include <bits/stdc++.h> #define TASK "" #define pb push_back #define F first #define S second #define FOR(i, a, b) for (int i=a; i<=b; i++) #define FOr(i, a, b) for (int i=a; i<b ; i++) #define FOD(i, a, b) for (int i=a; i>=b; i--) #define FOd(i, a, b) for (int i=a; i>b ; i--) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef vector<int> vi; const int N=1e6+7; const int MOD=1e9+7; const ll INF=(ll)1e18+7; int a[41][41][41][41]; ll s[41][41][41][41]; int m, n, p, q; void prepare() { for (int x = 1; x <= n; x++) for (int y = 1; y <= m; y++) for (int z = 1; z <= p; z++) for (int t = 1; t <= q; t++) { s[x][y][z][t] = a[x][y][z][t]; for (int mask = 1; mask < 16; mask++) { int nx = x - ((mask & 1) > 0); int ny = y - ((mask & 2) > 0); int nz = z - ((mask & 4) > 0); int nt = t - ((mask & 8) > 0); if (((nx != x) + (ny != y) + (nz != z) + (nt != t)) % 2) s[x][y][z][t] += s[nx][ny][nz][nt]; else s[x][y][z][t] -= s[nx][ny][nz][nt]; } //cout << s[x][y][z][t] << '\n'; } } ll getSum(int x, int y, int z, int t, int xx, int yy, int zz, int tt) { ll ans = s[xx][yy][zz][tt]; for (int mask = 1; mask < 16; mask++) { int nx = (mask & 1) > 0 ? x - 1 : xx; int ny = (mask & 2) > 0 ? y - 1 : yy; int nz = (mask & 4) > 0 ? z - 1 : zz; int nt = (mask & 8) > 0 ? t - 1 : tt; if (((nx != xx) + (ny != yy) + (nz != zz) + (nt != tt)) % 2) ans -= s[nx][ny][nz][nt]; else ans += s[nx][ny][nz][nt]; } return ans; } // ll bruforces(int x, int y, int z, int t, int xx, int yy, int zz, int tt) { // ll ans = 0; // for (int i = x; i <= xx; i++) // for (int j = y; j <= yy; j++) // for (int k = z; k <= zz; k++) // for (int l = t; l <= tt; l++) // ans += a[i][j][k][l]; // return ans; // } int main() { #ifdef TriPhan freopen("TEST.INP","r",stdin); freopen("TEST.OUT","w",stdout); #else ios_base::sync_with_stdio(0); cin.tie(0); #endif cin >> n >> m >> p >> q; for (int x = 1; x <= n; x++) for (int y = 1; y <= m; y++) for (int z = 1; z <= p; z++) for (int t = 1; t <= q; t++) cin >> a[x][y][z][t]; prepare(); // for (int x = 1; x <= n; x++) // for (int y = 1; y <= m; y++) // for (int z = 1; z <= p; z++) // for (int t = 1; t <= q; t++) // for (int xx = x; xx <= n; xx++) // for (int yy = y; yy <= m; yy++) // for (int zz = z; zz <= p; zz++) // for (int tt = t; tt <= q; tt++) // if ((getSum(x, y, z, t, xx, yy, zz, tt) != bruforces(x, y, z, t, xx, yy, zz, tt))) // cout << 'a'; int t; cin >> t; while (t--) { int x1, y1, z1, t1, x2, y2, z2, t2; cin >> x1 >> y1 >> z1 >> t1 >> x2 >> y2 >> z2 >> t2; cout << getSum(x1, y1, z1, t1, x2, y2, z2, t2) << '\n'; } }
Comments