数位DP

我们来逐步分析和解释这段数位DP的核心代码，并通过一个具体的例子来加深理解。

首先，来看代码的主要部分：

for (int pos = 0; pos < 30; pos++) 
    for (int tag1 = 0; tag1 < 2; tag1++) {
        ll &ans = dp[pos][tag1];
        ans = 0;
        int R1 = tag1 ? (a >> pos) & 1 : 1;
        int R2 = (b >> pos) & 1;
        for (int i = 0; i <= R1; i++) {
            if (i && R2) continue;
            ans += pos == 0 ? 1 : dp[pos - 1][tag1 && i == R1];
        }
    }

1. 外层循环 for (int pos = 0; pos < 30; pos++)

• pos 表示当前我们正在处理数字的第 pos 位。数字的位数上限为30，因为在题目中，我们关心的是30位二进制数（假设最大是 2^30，即大约十亿）。

2. 第二层循环 for (int tag1 = 0; tag1 < 2; tag1++)

• tag1 用来表示当前数字是否仍然符合上界限制：
  • tag1 = 1 表示当前数字仍然符合上界限制，即当前数字的高位还没有超过上限。
  • tag1 = 0 表示当前数字已经不再符合上界限制，即当前数字已经小于上限。

3. 计算 R1 和 R2

• R1 = tag1 ? (a >> pos) & 1 : 1;
  
  这一行代码计算的是 a 的第 pos 位。具体来说：

  • 如果 tag1 = 1，表示我们还没有超过上限，那么我们就按照 a 的第 pos 位来取 R1，即 (a >> pos) & 1。这表示我们只能取 a 当前这位的数字（0 或 1）。
  • 如果 tag1 = 0，表示我们已经不再受到上界限制，因此可以自由选择该位的数字，取 R1 = 1。

• R2 = (b >> pos) & 1;
  
  这一行代码计算的是 b 的第 pos 位，也就是区间的右端点。我们从 b 的二进制表示中取出第 pos 位，来判断当前位是否受限。

4. 内层循环 for (int i = 0; i <= R1; i++)

• 这里的 i 是候选的当前位的值。由于 R1 的限制，i 的取值只能在 [0, R1] 范围内。
  • 如果 R1 = 1，i 可以是 0 或 1。
  • 如果 R1 = 0，i 只能是 0。

5. 判断条件 if (i && R2) continue;

• 这一行代码的意思是，如果 i 为 1 且 R2 也为 1（即 b 的当前位是 1），我们跳过这一轮循环。
  • 由于我们要求 a & i = 0，所以 i 和 R2 同时为 1 时，不符合条件。

6. 动态转移 ans += pos == 0 ? 1 : dp[pos - 1][tag1 && i == R1];

• 如果 pos == 0，说明我们处理的是最底位，直接将答案加 1，表示当前位的合法数字（满足 a & i = 0 条件）。
• 如果 pos != 0，则递归地调用上一位的 dp 数值，更新当前的答案。
  • dp[pos - 1][tag1 && i == R1] 表示我们递归地去求解剩余的位数。
  • tag1 && i == R1 表示我们只有在 tag1 = 1 且 i == R1 时，才保持上界限制。

举例说明

假设我们有区间 [l, r]，并希望计算符合条件 a & i = 0 的数字个数。

例如，假设 a = 3 和 b = 7，我们需要计算区间 [0, 7] 中，符合 a & i = 0 的数字个数。

步骤：

1. 先看 a = 3，其二进制表示是 11。
2. 然后看 b = 7，其二进制表示是 111。

我们从高位开始逐位检查：

• 第 2 位（即二进制中的最左边一位）：

  • R1 = (a >> 2) & 1 = 0（因为 a = 3，二进制是 11，高位是 0）。
  • R2 = (b >> 2) & 1 = 1（因为 b = 7，二进制是 111，高位是 1）。
  • 所以我们可以在这一位选择 0。

• 第 1 位：

  • R1 = (a >> 1) & 1 = 1（因为 a = 3，第二位是 1）。
  • R2 = (b >> 1) & 1 = 1（因为 b = 7，第二位是 1）。
  • 所以我们可以选择 0 或 1，但如果选择 1 时需要满足 a & i = 0。

• 第 0 位：

  • R1 = (a >> 0) & 1 = 1（因为 a = 3，最低位是 1）。
  • R2 = (b >> 0) & 1 = 1（因为 b = 7，最低位是 1）。
  • 所以我们可以选择 0 或 1。

通过递归地处理这些位，最终得到符合 a & i = 0 的数字个数。

总结

这段代码的核心是通过动态规划逐位判断，处理每个数字的每一位，并根据当前位的限制（由 a 和 b 决定）来递归地计算结果。通过 dp[pos][tag1] 记录中间结果，并使用位操作来限制每一位的取值范围，从而高效地计算符合条件的数字个数。

发现整张图是一棵树，于是答案等于点数减边数。发现对于每个陆地 \((x,y)\)，如果不是 \((0,0)\)，则 \((x,y-1)\) 和 \((x-1,y)\) 恰有一块是陆地。

因此只需对子矩形的第一行和第一列计算答案即可。

对于只有一行的情况，仍然考虑点减边。

对于询问 \((a,l,r)\)，计算点数相当于计算 \(\sum_{i=l}^r [a~\text{and}~i=0]\)，计算边数相当于计算 \(\sum_{i=l}^{r-1}[a~\text{and}~(i~\text{or}~(i+1))=0]\)，可以使用数位 dp 计算。

时间复杂度 \(O(n*30)\)。

原题：p7970

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[30][2];

inline ll solve(int a, int b) {
    if (a < 0 || b < 0)
        return 0;
    for (int pos = 0; pos < 30; pos++)
        for (int tag1 = 0; tag1 < 2; tag1++) {
            ll &ans = dp[pos][tag1];
            ans = 0;
            int R1 = tag1 ? (a >> pos) & 1 : 1;
            int R2 = (b >> pos) & 1;
            for (int i = 0; i <= R1; i++) {
                if (i && R2)
                    continue;
                ans += pos == 0 ? 1 : dp[pos - 1][tag1 && i == R1];
            }
        }
    return dp[29][1];
}

inline ll solve2(int a, int b) {
    if (a < 0 || b <= 0)
        return 0;
    return solve(a, b | (b - 1));
}
int q;

int main() {
//  freopen("and.in", "r", stdin);
//  freopen("and.out", "w", stdout);
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        int l1, l2, r1, r2;
        scanf("%d%d%d%d", &l1, &l2, &r1, &r2);
        ll ans = solve2(r1, l2) - solve2(l1, l2);
        cerr<<"horizon ans="<<ans<<endl; 
        ans += solve2(r2, l1) - solve2(l2, l1);
        ans += (l1 & l2) == 0;
        printf("%lld\n", ans);
    }
}