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.

Author: bedao

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;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.