[yLOI2019] 棠梨煎雪

GitHub跳转原题关系图 Canvas 关系图返回列表

每个串压成 0/1 两个位掩码，线段树按位或合并区间约束，统计兼容二进制串数量。

OJ: luogu

题目 ID: P5522

难度:提高

标签:线段树位运算状态压缩区间合并字符串

日期: 2026-07-16 23:59

前置题目

luogu P1558色板游戏位掩码状态的线段树维护，本题改为单点改+按位或合并

形式化题目

有 $m$ 个长度为 $n$ 的字符串，每个位置是 0、1 或 ?， $n \leqslant 30$ 。支持两类操作：

询问区间 $[l, r]$ ：求有多少个 0/1 串 $S$ ，满足区间内每个字符串都能把 ? 替换成 0 或 1 后变成 $S$ ；
把某一个字符串整体替换成新串。

最后把所有询问答案异或起来输出。

本质上：每个带 ? 的串是一个「位置约束的集合」——位置要么被固定为 0、要么被固定为 1、要么自由。询问就是求区间内这些约束集合的交集大小。

思路

先看一个直接按题面定义的朴素解：

cpp

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
60
61
62
63
64
65
66
67
68
69
70
71/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 23:00
 * update_at: 2026-08-12 22:12
 */
// brute.cpp：小数据暴力解，使用 01 序列递归枚举候选串 S，用来理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAX_LEN = 35;

int n, m, q;
char str[MAXN][MAX_LEN]; // str[i]：第 i 年信的内容（0 / 1 / ?）
int choose[MAX_LEN];     // choose[j]：候选串 S 第 j 位的取值，0 或 1

// 检查当前完整候选串 choose[0..n-1] 是否兼容 [l, r] 内的所有信。
// 对每个位置：信里是 '0' 则 S 该位必须为 0，是 '1' 则必须为 1，是 '?' 则无限制。
bool check(int l, int r) {
    for (int i = l; i <= r; i++) {
        for (int j = 0; j < n; j++) {
            if (str[i][j] != '?' && str[i][j] - '0' != choose[j])
                return false;
        }
    }
    return true;
}

// dfs(dep)：这一层枚举候选串第 dep 位取 0 还是 1。
// 生成完整 n 位候选串后，在叶子节点统一检查并统计答案。
void dfs(int dep, int l, int r, int& cnt) {
    if (dep == n) {
        if (check(l, r))
            cnt++;
        return;
    }
    for (int b = 0; b <= 1; b++) {
        choose[dep] = b;
        dfs(dep + 1, l, r, cnt);
    }
}

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

    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
        cin >> str[i];

    int ans_xor = 0; // 所有查询答案的异或和
    while (q--) {
        int opt;
        cin >> opt;
        if (opt == 1) {
            // 修改：直接覆盖第 pos 年的信
            int pos;
            cin >> pos >> str[pos];
        } else {
            // 查询：枚举全部 2^n 个候选串 S，统计与 [l, r] 内所有信兼容的个数
            int l, r, cnt = 0;
            cin >> l >> r;
            dfs(0, l, r, cnt);
            ans_xor ^= cnt;
        }
    }
    cout << ans_xor << '\n';
    return 0;
}

这个暴力把每次询问看成一串 01 选择：choose[j] = 0/1 表示候选串 $S$ 第 $j$ 位的取值。递归先生成完整的 $n$ 位候选串，到叶子节点再与 $[l, r]$ 内每一封信逐位检查是否兼容，统计兼容的候选串个数。一次询问 $O(2^n \cdot n \cdot (r-l+1))$ ，只适合 $n \leqslant 6$ 左右的小数据，但它是独立于位掩码公式的验证基准。

瓶颈在于逐候选串、逐信、逐位地检查。优化思路是把一封信的约束压进两个位掩码（每个位置一个 bit， $n \leqslant 30$ 正好放进一个 32 位整数）：

zero：出现 0 的位置集合；
one：出现 1 的位置集合；
? 不贡献任何位。

编码动作本身很简单：约定字符串第 $i$ 个字符（从 0 开始数）对应二进制第 $i$ 位，遍历字符串时用 1 << i 把对应位置 1：

cpp

1
2
3
4
5
6int z = 0, o = 0;
for (int i = 0; i < n; i++) {
    if (t[i] == '0') z |= (1 << i);       // 第 i 位固定为 0
    else if (t[i] == '1') o |= (1 << i);  // 第 i 位固定为 1
    // '?' 不设置任何位
}

以 010 为例：第 0、2 个字符是 0，把 bit 0 与 bit 2 置 1，得 $z = 0\text{b}101$ ；第 1 个字符是 1，得 $o = 0\text{b}010$ 。下表中集合 {1, 3}、{2} 正是这两个掩码转成 1-indexed 位置后的写法。这样每一封信就压缩成两个 32 位整数，线段树节点直接存这两个值。

关键观察是区间合并就是按位或： $S$ 同时兼容区间内每一封信，等价于 $S$ 满足所有信约束的并集。于是区间 $[l, r]$ 的约束是：

Z = \bigvee_{i=l}^{r} z(s_i), \qquad O = \bigvee_{i=l}^{r} o(s_i)

答案公式：若 $Z \cap O \neq \varnothing$ （某一位同时被固定为 0 和 1，说明区间内有两封信冲突）答案为 0；否则被固定过的位置有 $|Z \cup O|$ 个，剩下 $n - |Z \cup O|$ 个位置自由，答案为 $2^{\,n - |Z \cup O|}$ 。

「按位或合并」满足结合律、单位元为 0（空集合），且操作形态是单点修改 + 区间查询——这正是线段树的标准形态。每个节点存 (zero, one) 两个掩码，push_up 时分别 OR；一次询问只访问 $O(\log m)$ 个整段节点。

以样例的三封信为例（位置 1…3），掩码编码与合并过程如下：

第一张表展示每封信编码出的两个掩码：

串	zero（固定为 0 的位置）	one（固定为 1 的位置）
010	{1, 3}	{2}
0?0	{1, 3}	∅
1?0	{3}	{1}
0??（修改后的 s3）	{1}	∅

第二张表展示 4 次询问的合并结果：

询问	合并 Z	合并 O	Z∩O	自由位	答案
[1,2]	{1, 3}	{2}	∅	0	1
[2,3]	{1, 3}	{1}	{1}	—	0
修改后 [2,3]	{1, 3}	∅	∅	1	2
修改后 [1,3]	{1, 3}	{2}	∅	0	1

观察要点：第二次询问中位置 1 被 s2 固定为 0、又被 s3 固定为 1，Z ∩ O ≠ ∅ 直接判 0；把 s3 改成 0?? 后冲突消除，位置 2 成为唯一的自由位，答案变成 $2^1 = 2$ 。这正是「OR 合并 + 冲突判定 + 2 的幂」三条规则在样例上的体现，异或总答案为 $1 \oplus 0 \oplus 2 \oplus 1 = 2$ 。

下面这张图展示一棵规模为 8 的线段树，节点上的数字是它代表的区间：

任意询问区间都能拆成 $O(\log m)$ 个整段节点。例如查询 $[2,7]$ 会命中 [2,2]、[3,4]、[5,6]、[7,7] 四个整段节点，各花 $O(1)$ 做两次 OR 合并，这就是 $O(\log m)$ 的来源：不需要逐个访问区间里的每封信。

代码

cpp

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 23:00
 * update_at: 2026-08-15 22:30
 */
// main.cpp：P5522 正式主解。线段树按位或合并区间的 0/1 约束，单点修改、区间查询。
#include <bits/stdc++.h>
using namespace std;

// 按位或合并区间约束的线段树（单点修改、区间查询）
struct SegmentTreeBitOr {
    // 线段树节点：zero / one 为区间内所有串的约束掩码
    struct Node {
        int zero = 0;   // 区间内被固定为 0 的位置集合（位掩码）
        int one = 0;    // 区间内被固定为 1 的位置集合（位掩码）

        // 合并两个孩子：两个掩码分别按位或，合并结果与顺序无关
        Node operator+(const Node &other) const {
            return Node{zero | other.zero, one | other.one};
        }
    };

    // 左儿子 / 右儿子的节点编号
    static int lson(int p) { return p << 1; }
    static int rson(int p) { return p << 1 | 1; }

    // 区间 [l, r] 的中点
    static int mid(int l, int r) { return (l + r) >> 1; }

    int n = 0;              // 区间大小
    vector<Node> tree;      // 线段树数组

    SegmentTreeBitOr(int n = 0) {
        init(n);
    }

    void init(int size) {
        n = size;
        tree.assign(n * 4 + 5, Node{});
    }

    // 上推：用两个孩子合并出当前节点
    void push_up(int p) {
        tree[p] = tree[lson(p)] + tree[rson(p)];
    }

    // 把字符串 t 编码成两个位掩码：第 i 个字符对应二进制第 i 位（从 0 开始）。
    // '0' 把第 i 位置进 zero，'1' 把第 i 位置进 one，'?' 不设置任何位。
    static Node encode(const string &t) {
        int z = 0, o = 0;
        for (int i = 0; i < (int)t.size(); i++) {
            if (t[i] == '0') z |= (1 << i);
            else if (t[i] == '1') o |= (1 << i);
        }
        return Node{z, o};
    }

    // 用字符串数组 s 建树（下标从 1 开始）
    void build(const vector<string> &s, int l, int r, int p = 1) {
        if (l == r) {
            tree[p] = encode(s[l]);
            return;
        }
        int m = mid(l, r);
        build(s, l, m, lson(p));
        build(s, m + 1, r, rson(p));
        push_up(p);
    }

    // 单点修改：把位置 pos 的字符串整体替换为 t
    void modify(int pos, const string &t, int l, int r, int p = 1) {
        if (l == r) {
            tree[p] = encode(t);
            return;
        }
        int m = mid(l, r);
        if (pos <= m) modify(pos, t, l, m, lson(p));
        else modify(pos, t, m + 1, r, rson(p));
        push_up(p);
    }

    // 区间查询：返回 [ql, qr] 内所有约束 OR 合并后的结果
    Node query(int ql, int qr, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) return tree[p];

        int m = mid(l, r);
        Node answer;
        if (ql <= m) answer = answer + query(ql, qr, l, m, lson(p));
        if (qr > m) answer = answer + query(ql, qr, m + 1, r, rson(p));
        return answer;
    }
};

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

    int n, m, q;
    cin >> n >> m >> q;

    vector<string> s(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> s[i];
    }

    SegmentTreeBitOr seg(m);
    seg.build(s, 1, m);

    int ans_xor = 0; // 所有查询答案的异或和
    while (q--) {
        int opt;
        cin >> opt;
        if (opt == 1) {
            int pos;
            string t;
            cin >> pos >> t;
            seg.modify(pos, t, 1, m);
        } else {
            int l, r;
            cin >> l >> r;
            auto res = seg.query(l, r, 1, m);
            if ((res.zero & res.one) == 0) {
                // 无冲突：没有被任何串固定的位置都可自由选 0/1，答案 = 2^自由位个数
                int free_cnt = n - __builtin_popcount(res.zero | res.one);
                ans_xor ^= (1 << free_cnt);
            }
            // 若 zero & one != 0，某一位同时被固定为 0 和 1，答案为 0，异或 0 不变
        }
    }

    cout << ans_xor << '\n';
    return 0;
}

复杂度

时间：建树 $O(m)$ ；单次修改或询问 $O(\log m)$ ；总复杂度 $O(m + q \log m)$ 。
空间：线段树四倍数组 $O(m)$ ，另有 $O(nm)$ 的原串数组（ $n \leqslant 30$ 视为常数），共 $O(m)$ 。

总结

这道题把「带 ? 的字符串区间约束」压缩成「两个位掩码 + 按位或合并」：交集语义对应 OR 合并，冲突判定与 $2^{\text{自由位}}$ 都是 $O(1)$ 的位运算。 $n \leqslant 30$ 是位压进 32 位整数的关键前提，OR 的结合律则让它无缝套进线段树。rbook 的《线段树：单点修改与区间查询》讲解了同一种 push_up / build / 单点改 / 区间查模板结构，本解即由该模板（segtree-point-add-range-sum）把「加合并」改成「OR 合并」而来。

图示解析

这张 ASCII 图展示整道题的解题路线：从暴力枚举出发，到位掩码 + 线段树解法：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21朴素暴力（brute.cpp）
  枚举全部 2^n 个候选串 S（choose[j] = 第 j 位取 0 或 1）
  叶子节点逐信逐位检查兼容性      O(2^n * n * 区间长) 每次询问
        |
        | 瓶颈：候选串指数级、区间逐串线性级，都不行
        v
关键观察
  一封信的约束 = 两个位置集合：zero（固定为 0）、one（固定为 1）
  区间内所有信同时满足 ⇔ 约束取并集 ⇔ 掩码按位或
  z∩o ≠ ∅（某位同时被固定为 0 和 1）→ 答案 0
  否则答案 = 2^(n - |z∪o|)（自由位各两种取法）
        |
        v
线段树（main.cpp）
  节点存区间 (zero, one) 两个掩码
  push_up：左右儿子分别按位或合并
  修改：叶子重新编码，路径上 push_up 上推
  查询：区间拆成 O(log m) 个整段节点，OR 进累计变量
        |
        v
复杂度 O((m + q) log m)，空间 O(m)

观察要点：图中三条主线分别对应「暴力慢在哪里」「观察到的合并规则」「正式解如何利用这个规则」。合并规则是这道题的灵魂——交集大小的语义落到位掩码上就是 OR；冲突判定与 $2^{\text{自由位}}$ 公式只是 OR 之后的两次位运算。

P5522 [yLOI2019] 棠梨煎雪

题目背景

岁岁花藻檐下共将棠梨煎雪，
自总角至你我某日辗转天边。
天淡天青，宿雨沾襟，
一年一会信笺却只见寥寥数言。

——银临《棠梨煎雪》

题目描述

扶苏正在听《棠梨煎雪》的时候，@spitfirekindergarten 发来一道 IOI2018 集训队作业题：我切了这集训队题，辣鸡扶苏快过来做题。扶苏定睛一看，这不 s* 题嘛，写了一发交上去才发现自己看错题目了。但是写完的代码不能浪费，于是就有了这道题。

歌词中的主人公与她的朋友一年会有一次互相写信给对方，一共通信了 $m$ 年。为了简化问题，我们认为她们每封信的内容都是一条二进制码，并且所有二进制码的长度都是 $n$ 。即每封信的内容都是一个长度为 $n$ 的字符串，这个字符串只含字符 $0$ 或 $1$ 。

这天她拿出了朋友写给她的所有信件，其中第 $i$ 年的写的信件编号为 $i$ 。由于信件保存时间过久，上面有一些字符已经模糊不清，我们将这样的位置记为 $?$ ， $?$ 字符可以被解释为 $0$ 或 $1$ 。由于她的朋友也是人，符合人类的本质，所以朋友在一段连续的时间中书写的内容可能是相同的。现在她想问问你，对于一段连续的年份区间 $[l,r]$ 中的所有信件，假如朋友在这段时间展示了人类的本质，所写的是同一句话，那么这一句话一共有多少种可能的组成。也即一共有多少字符串 $S$ ，满足在这个区间内的所有信件的内容都可能是 $S$ 。

一个长度为 $n$ 的只含 $0,1,?$ 的字符串 $A$ 可能是一个字符串 $B$ 当且仅当 $B$ 满足如下条件：

$B$ 的长度也是 $n$ 。
$B$ 中只含字符 $0,1$ 。
$A$ 中所有为 $0$ 的位置在 $B$ 中也是 $0$ 。
$A$ 中所有为 $1$ 的位置在 $B$ 中也是 $1$ 。
$A$ 中为 $?$ 的位置在 $B$ 中可以为 $0$ 也可以是 $1$ 。

同时她可能会突然发现看错了某年的信的内容，于是她可能会把某一年的信的内容修改为一个别的只含 $0$ , $1$ , $?$ 的长度为 $n$ 的字符串。

输入格式

每个输入文件中都有且仅有一组测试数据。

输入数据第一行为三个用空格隔开的整数，分别代表代表字符串长度 $n$ ，字符串个数 $m$ 和操作次数 $q$ 。

下面 $m$ 行，每行是一个长度为 $n$ 的字符串，第 $(i + 1)$ 行的字符串 $s_i$ 代表第 $i$ 年信的内容。

下面 $q$ 行，每行的第一个数字是操作编号 $opt$ 。

如果 $opt=0$ ，那么后面接两个整数 $[l,~r]$ ，代表一次查询操作。
如果 $opt=1$ ，那么后面接一个整数 $pos$ ，在一个空格后会有一个长度为 $n$ 的字符串 $t$ ，代表将第 $pos$ 个字符串修改为新的字符串 $t$ 。

输出格式

为了避免输出过大，请你输出一行一个数代表所有查询的答案异或和对 $0$ 取异或的结果。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

样例 1 解释

对于第一次询问，只有串 $010$ 符合要求。
对于第二次询问，由于第二个串的第一位为 $0$ ，第三个串的第一位为 $1$ ，故没有串符合要求。
修改后将第三个串修改为 $0??$ 。
对于第四次询问，有两个串符合要求，分别为 $000$ 和 $010$ 。
对于第五次询问，只有 $010$ 符合要求。

故答案为 $1,0,2,1$ ，他们的异或和再异或 $0$ 的值为 $2$ 。

数据规模与约定

本题采用多测试点捆绑测试，共有 7 个子任务。

子任务编号	$m = $	$q = $	$n = $	子任务分数
$1$	$1$	$0$	$1$	$5$
$2$	$102$	$102$	$10$	$10$
$3$	$1003$	$1003$	$10$	$15$
$4$	$1004$	$10004$	$30$	$15$
$5$	$100005$	$500005$	$1$	$15$
$6$	$100006$	$50006$	$30$	$10$
$7$	$100007$	$1000007$	$30$	$30$

对于全部的测试点，保证：

$1 \leq m \leq 10^5 + 7$ ， $0 \leq q \leq 10^6 + 7$ ， $1 \leq n \leq 30$ 。
$0 \leq opt \leq 1$ ， $1 \leq pos \leq m$ ， $1 \leq l \leq r \leq m$ 。
$s_i, t$ 的长度均为 $n$ 且只含有字符 0,1,?。
输入字符串的总长度不超过 $5 \times 10^6$ 。数据在 Linux 下生成，即换行符不含 \r。

提示

请注意常数因子对程序效率造成的影响。
请注意数据读入对程序效率造成的影响。
请注意输入的问号为英文问号，即其 ASCII 值为 $63$ 。

注: 为减少错误做法的通过率，时限于 2020 年 7 月由 2000ms 改为 1500ms。

[yLOI2019] 棠梨煎雪

目录

形式化题目

思路

代码

复杂度

总结

图示解析