ALGORITHM NOTES阅读地图
11个主要章节
1段代码示例
8组图片与图表

先明确状态与不变量，再对照手算、证明、边界和实现。

章节速览11 节 · 展开选择

给定一批区间 AND 的结果，反过来恢复一个数组，看起来像是在解一组相互牵制的方程。真正决定做法的是一个不对称关系：结果某位为 1，区间里的每个位置都必须为 1；结果某位为 0，只需要区间里有一个位置为 0。

这篇衔接前缀和与差分、线段树的区间合并与按位计数。我们不急着维护区间修改，先找出任何可行解都躲不开的位，再检验这些必要条件有没有互相冲突。

阅读前

理解 AND 与差分

会把整数拆成二进制位，并用两个端点记录一次区间加一。

关键问题

哪些一无法撤销

先放入全部被强制的一，其余位保持零，再寻找零位约束的见证。

完成标志

证明失败就是无解

说明候选数组为什么是按位最小解，以及继续加一为何救不了一次失败。

从一个覆盖图开始

先看本站自拟的五位置例子：区间 [1,3] 的 AND 要等于 2，[2,4] 要等于 6，[3,5] 要等于 4。只需要关注低三位。

五个位置上，数值二的位被前两条约束强制覆盖到一至四，数值四的位被后两条强制覆盖到二至五，最小候选为二、六、六、六、四。
同一位置被不同约束要求的位要取并集，所以得到 2、6、6、6、4。图中空格表示没有约束强制这一位为一，构造时让它保持零。查看原图

关键不是“把一个区间赋成 q”。位置 2 同时参与要求 2 和要求 6 的区间，它应该兼容两边的一位要求；直接赋值会覆盖已经得到的信息。

官方题目与范围

题目为 Codeforces 482B Interesting Array。以下元信息与约束于 2026-10-20 根据官方题目页核对；推导、例子与图均为本站原创。

项目 官方信息
难度 1800
标签 constructive algorithms、data structures、trees
数组长度与约束数 1 ≤ n,m ≤ 100000
每条约束 1 ≤ l ≤ r ≤ n，0 ≤ q < 2^30
输出 任意满足全部约束、元素处于 [0,2^30) 的数组；无解输出 NO
时空限制 1 秒、256 MB

用自己的话概括任务：对每条 (l,r,q)，都要使 a[l] & a[l+1] & … & a[r] == q。只求一个可行数组，不要求它是唯一解。

朴素尝试为什么容易绕远

穷举每个元素有 2^(30n) 种候选，显然无法使用。另一种直觉是从全零数组开始，对每条约束逐个位置执行 a[i] |= q，最后逐区间计算 AND。这种思路的构造方向是对的，但区间很长时，两阶段各自都可能花 O(nm)。

还可以用支持区间 OR 与区间 AND 查询的线段树，得到约 O((n+m)log n) 的做法。本题所有约束预先给出，构造结束后也没有在线修改需求；按位拆开以后，差分与前缀计数就足够了。数据结构服务于信息流，不必因为题目涉及区间就立刻加懒标记。

一位等式有两种含义

固定二进制位 b，让 x[i] 表示 a[i] 的这一位。区间 AND 等于目标位，可分为：

q 的第 b 位 对区间内 x 的要求 构造时怎么处理
1 所有 x[l..r] 都为 1 把整个区间标成被强制的一
0 至少存在一个 x[i]=0 不急着指定哪个位置，留到构造后验证

不要把第二行误读成“所有位置为零”。例如 6 & 4 == 4，结果的数值二这一位为零，但数值 6 的那一位仍然为一。

对每个位，我们只把被任一“一位约束”覆盖的位置设为 1，其他位置全设为 0。不同位彼此独立，最后把它们拼成整数。

用差分生成强制位置

对当前位建立长度为 n+2 的差分数组 diff。每当一条约束的这一位为 1，就执行：

diff[l] += 1，diff[r+1] -= 1。

扫描位置 1 到 n，累加得到覆盖次数 cover。只要 cover > 0，至少有一条必要条件要求这一位为 1，于是执行 a[i] |= mask。这里 mask = 1u << b。

差分记录的是覆盖次数，不能把端点的 +1/-1 换成 OR：重叠区间需要在各自结束时正确撤销一份覆盖，OR 本身没有对应的减法。

同时生成前缀计数 ones[i]，表示位置 [1,i] 中当前位为 1 的位置数。对目标位为零的约束，只需检查：

ones[r] - ones[l-1] < r-l+1。

严格小于区间长度意味着至少留下一个零。如果等于区间长度，就不存在零位见证。

把五位置例子算完

对数值 4 这一位，一位约束是 [2,4] 和 [3,5]，所以覆盖次数依次为 0,1,2,2,1。覆盖两次不会把二进制位变成 2，它仍然只表示“必须为一”。数值 2 这一位由 [1,3] 和 [2,4] 强制覆盖。

位置 i数值 4 的位数值 2 的位数值 1 的位二进制 a[i]十进制 a[i]
10100102
21101106
31101106
41101106
51001004

再验三个原始区间：2 & 6 & 6 = 2；6 & 6 & 6 = 6；6 & 6 & 4 = 4。三个目标都实现了，但不同区间的零位见证可能落在不同位置。

本例数值 4 的位前缀计数是 0,0,1,2,3,4，其中第一项对应空前缀。约束 [1,3] 在这一位要求零，区间一的数量为 2-0=2，小于长度 3，所以位置 1 提供了见证。

为什么这个候选足以决定有解与否

“先试一个数组，失败就输出 NO”通常不可靠。这里可靠，是因为构造没有任意选择需要回退的决定。

固定一位，记强制构造为 f，任取一个可行解为 s。只要 f[i]=1，就有一条覆盖 i 的一位约束；这条约束迫使任何可行解的 s[i] 都为 1。因此逐位置有 f[i]≤s[i]。

这称为按位偏序下的最小构造：它包含任何解都必须包含的一位，并把其余位留为零。这里比较的是一位是否被包含；不能用整数的数值大小代替按位包含关系，例如数值 1<2 并不表示 1 的一位包含在 2 里面。

分两种情况讨论验证结果：

  1. 全部零位约束都通过。目标为一的位由构造保证全部为一，目标为零的位又有见证，因此每条约束的每个位都正确，候选数组就是可行解。
  2. 某个零位约束失败。其区间每个位置都已被迫为一；任何可行解也必须在这些位置放一，区间 AND 的这一位只能是一，与目标零矛盾。增加其他一位更无法补出一个零，所以根本不存在解。

这个证明同时说明：只要有解，我们输出的数组在逐元素的按位包含关系下不大于任何解，但题目并不要求读者实现额外的最小化目标。

三条约束就能产生矛盾

只看最低位：[1,2] 要求 1，[2,3] 也要求 1，[1,3] 却要求 0。前两条已经强制三个位置全为 1，第三条无处寻找零。

最低位上，区间一到二和二到三都要求一，联合强制三个位置全为一，导致一到三要求零的约束没有零位置见证，因此无解。
失败区间展示的不是一次不幸的猜测，而是一份矛盾证书：每个位置的一都由其他约束强制，任何替代数组都无法把它改回零。查看原图

验证只在需要零位见证的地方检查即可；目标位为一的区间已经被差分构造完整覆盖。实现时也可以额外检查所有区间 AND，但不需要重复做同一份保证。

完整 C++17 实现

下面保留 30 个二进制位。每一轮复用 diff 和 ones，输入约束只存一份。所有位置使用一基下标，r+1 最远到 n+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

struct Constraint {
    int l;
    int r;
    std::uint32_t q;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    if (!(std::cin >> n >> m)) return 0;
    std::vector<Constraint> constraints(m);
    for (auto& c : constraints) std::cin >> c.l >> c.r >> c.q;

    std::vector<std::uint32_t> answer(n + 1, 0);
    std::vector<int> diff(n + 2, 0), ones(n + 1, 0);

    for (int bit = 0; bit < 30; ++bit) {
        const std::uint32_t mask = std::uint32_t{1} << bit;
        std::fill(diff.begin(), diff.end(), 0);
        for (const auto& c : constraints) {
            if ((c.q & mask) != 0) {
                ++diff[c.l];
                --diff[c.r + 1];
            }
        }

        int cover = 0;
        ones[0] = 0;
        for (int i = 1; i <= n; ++i) {
            cover += diff[i];
            const int forced = (cover > 0 ? 1 : 0);
            if (forced != 0) answer[i] |= mask;
            ones[i] = ones[i - 1] + forced;
        }

        for (const auto& c : constraints) {
            if ((c.q & mask) == 0 &&
                ones[c.r] - ones[c.l - 1] == c.r - c.l + 1) {
                std::cout << "NO\n";
                return 0;
            }
        }
    }

    std::cout << "YES\n";
    for (int i = 1; i <= n; ++i) {
        if (i > 1) std::cout << ' ';
        std::cout << answer[i];
    }
    std::cout << '\n';
    return 0;
}

边界、成本与容易误写的地方

每个位扫描约束两次、位置一次，因此时间为 O(30(n+m))；30 是本题值域决定的位数。空间为 O(n+m)，没有保留 30 份差分或前缀数组。覆盖次数和前缀计数最多分别为 m 与 n，普通 int 足够；元素明确采用无符号 32 位类型，最高处理到第 29 位。

情况 应有行为 常见错误
全部 q 为零 全零候选立即满足 误以为零约束不提供信息，完全省略验证
单点区间 该元素必须精确等于 q 只构造一位，忽略其他约束强制的额外位
相同区间不同 q 一定无解 后来的赋值覆盖前面的要求
重叠的一位区间 覆盖次数可以大于 1 把次数直接当二进制位，或用 XOR 切换
r 等于 n 在 diff[n+1] 撤销覆盖 只分配 n 或 n+1 个槽位
q 含第 29 位 正常参与全部判断 只循环到第 28 位，或写浮点 pow 代替位移
没有被强制的位置 所有位保持零 为了“更像一般数组”而随意补一

这套论证依赖本题 AND 的一位约束形式。把 AND 改成 XOR，或再加入和值、元素互异等条件，按位最小构造不再自动解决整个问题；增加一个未被强制的一也未必保持那些额外条件。

验证记录与自检

验证程序位于 tests/verify-interesting-array-article.cjs，会提取上面的原样实现，以 -std=c++17 -O2 -Wall -Wextra -pedantic -Werror 编译。MinGW g++ 13.1.0 无警告编译通过；1,222 个实例中，1,208 个使用完整数组穷举参考，合计枚举 457,982 个候选数组，另有 5 个 n=m=100000 的边界实例。

小实例逐条计算 AND，既核对是否有解，也核对输出是否等于全部可行数组逐位置取 AND 得到的最小数组。它们包含 776 个系统化约束组合、400 个预定种子的随机系统及顺序翻转检查。大实例覆盖全位重叠、全零约束、仅最右位置留零、第 29 位才产生矛盾及混合长度区间；另用原始区间按位置 OR 的构造及独立稀疏表区间查询核验，不把同一份逐位差分当作参考答案。

这些检查验证的是本题有限整数模型与代码；不把本机运行时间当作所有评测机的耗时保证。独立运行命令为 node tests/verify-interesting-array-article.cjs。

自检：q 的一位为零，能直接给整个区间清零吗？

不能。它只要求至少一个零；其他位置可能被不同的一位约束强制为一。先构造所有强制位，再检查是否还留有零位见证。

自检：最小候选失败后，多放几个一有帮助吗？

没有。失败意味着某个要求零的区间已经全为被强制的一。添加一无法产生零；删除其中任何一又会破坏至少一条必要条件。

自检：为什么每一位都可以从头清空差分？

按位 AND 没有进位，不同位的约束独立。当前位完成后，其结果已经写进 answer；下一位需要重新计算自己的覆盖次数。

继续阅读时，可以回到交替位运算线段树，比较“需要动态维护的区间合并”与“所有约束一次给出”的区别；再看区间取模与均摊分析，比较结构如何由真正需要维护的信息决定。