思路与算法

使用0基坐标后白格满足x&y=0。白格图是一棵树：除(0,0)外，每个白格恰能向上或向左连一个父格，由两坐标最低有效1位较低的一侧决定。矩形截出的森林分量数等于父格落在矩形外的白格数。只需数首行的向上父格及首列的向左父格，条件化为另一坐标必须为某个2次幂的倍数且与边界坐标按位与0，用逐位前缀计数求闭区间数量。

正确性说明

递减某坐标会把其最低1以下位变成1；在x&y=0下，最低有效位较高的一侧递减会碰到另一侧最低1，较低一侧递减仍为白格，故父格唯一。父边严格减坐标和，无环且通根。有限矩形的每个森林分量有且仅有一个父格越界的顶点，边界计数即分量数；包含原点时额外计原根1。

复杂度

每查询两次边界、各两个二进制前缀计数，O(log(max坐标))时间，q条总O(qlogV)，辅助O(1)空间，输入逐条处理。

易错点

原输入1基，须先减1。全黑矩形答案0。坐标0没有最低有效1，单独处理；计数包含y=0这种可整除任意2幂的情形。所有移位量保持小于64。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using U = unsigned long long;
U countMask(U R, U mask) {
    U ans = 0;
    for (int b = 31; b >= 0; b--) {
        if (R >> b & 1) {
            int free = __builtin_popcount((unsigned)((~mask) & ((1ULL << b) - 1)));
            ans += 1ULL << free;
            if (mask >> b & 1)
                return ans;
        }
    }
    return ans + 1;
}
U prefix(long long R, U forbidden, int shift) {
    if (R < 0)
        return 0;
    return countMask((U)R >> shift, forbidden >> shift);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        U x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        --x1;
        --y1;
        --x2;
        --y2;
        U ans = 0;
        if (x1) {
            int sh = __builtin_ctzll(x1) + 1;
            ans += prefix(y2, x1, sh) - prefix((long long)y1 - 1, x1, sh);
        }
        if (y1) {
            int sh = __builtin_ctzll(y1) + 1;
            ans += prefix(x2, y1, sh) - prefix((long long)x1 - 1, y1, sh);
        }
        if (!x1 && !y1)
            ans++;
        cout << ans << '\n';
    }
}