[yLOI2019] 棠梨煎雪

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

线段树按位合并区间字符串的 0/1 约束，统计所有兼容二进制串的数量。

OJ: luogu

题目 ID: P5522

难度:省选/提高

标签:线段树位运算字符串异或python

日期: 2026-07-16 23:59

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

每封信是由 0/1/? 组成的字符串，区间内所有信件必须可能对应同一个二进制串；支持修改一封信，并把所有查询答案异或后输出。

思路

对每个字符串记录两个位掩码：出现 0 的位置集合 zeros、出现 1 的位置集合 ones。区间合并分别按位或；若 zeros & ones 非零，某一位同时被固定为 0 和 1，答案为 0。否则没有被固定的位置都可自由选择，答案是 2 ** (n - (zeros | ones).bit_count())。

Python 知识

  • int 位运算一次处理最多 30 个位置。
  • 迭代线段树查询避免递归，适合最多百万次操作。
  • bit_count() 和 1 << k 直接表达自由位数量与方案数。

代码

python
import sys
from bisect import bisect_right


input = sys.stdin.buffer.readline
n, strings, operations = map(int, input().split())
size = 1
while size < strings:
    size <<= 1
zero = [0] * (2 * size)
one = [0] * (2 * size)


def encode(text):
    zeros = ones = 0
    for index, char in enumerate(text):
        bit = 1 << index
        if char == 48:
            zeros |= bit
        elif char == 49:
            ones |= bit
    return zeros, ones


for index in range(strings):
    zero[size + index], one[size + index] = encode(input().strip())
for index in range(size - 1, 0, -1):
    zero[index] = zero[index * 2] | zero[index * 2 + 1]
    one[index] = one[index * 2] | one[index * 2 + 1]

answers = 0
for _ in range(operations):
    operation = input().split()
    if operation[0] == b'1':
        position = int(operation[1]) - 1
        zero[size + position], one[size + position] = encode(operation[2])
        node = (size + position) // 2
        while node:
            zero[node] = zero[node * 2] | zero[node * 2 + 1]
            one[node] = one[node * 2] | one[node * 2 + 1]
            node //= 2
        continue
    left, right = int(operation[1]) - 1 + size, int(operation[2]) + size
    zeros = ones = 0
    while left < right:
        if left & 1:
            zeros |= zero[left]
            ones |= one[left]
            left += 1
        if right & 1:
            right -= 1
            zeros |= zero[right]
            ones |= one[right]
        left //= 2
        right //= 2
    answers ^= 0 if zeros & ones else 1 << (n - (zeros | ones).bit_count())
print(answers)

原有 C++ 版本仍保留：

cpp
/**
 * 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-07-16 23:46
 * update_at: 2026-07-16 23:46
 */
#include <bits/stdc++.h>
using namespace std;

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

    return 0;
}

复杂度

每次修改或查询 O(log m)，编码每个字符串 O(n)，空间 O(m)。

总结

把字符串约束转换为两个集合，区间问题就变成位掩码的 OR 与冲突检测。