题目地址：P5522 [yLOI2019] 棠梨煎雪 – 洛谷 – 计算机科学教育新生态

题意

给定 $m$ 个长度为 $n$ 的 $01$ 串。存在某些位置为 ?，每个 ? 独立，既可以取 $0$，也可以是 $1$.

维护 $q$ 次操作，每次操作可能为：

• 区间查询：查询有多少个只包含 $01$ 的串 $s$ 满足：存在一种对 ? 的赋值方法，使得区间内的每个 $01$ 串都能与 $s$ 完全匹配。
• 单点修改：把第 $i$ 个串替换为给定的新串。

$1\leq m\leq 10^5, 1\leq q\leq 10^6, 1\leq n\leq 30$.

分析

区间查询 $+$ 单点修改 $\Longrightarrow$ 线段树。

主要问题在：如何处理对 $[l, r]$ 进行的查询操作。

若区间中存在两个串 $s_i, s_j$，存在 $k$ 使得 $s_i[k]$ 和 $s_j[k]$ 一个是 $0$，另一个是 $1$，那么合法串的个数为 $0$。

否则，只需要知道，有多少个 $k$ 满足：$\forall i, j\in [l, r]$，$s_i[k]=s_j[k]=$ ?.

若有 $x$ 个满足要求的 $k$，则区间询问的答案是 $2^{x}$.

维护信息

考虑对 $m$ 个字符串建立线段树，以编号为下标。

发现 $1\leq n\leq 30$，可以用 int 类型存储二进制压缩后的的状态。

考虑用线段树：$v_0$ 记录必须为 $0$ 的位置，$v_1$ 记录必须为 $1$ 的位置。

具体地，设线段树的 $i$ 号节点代表的区间为 $[l_i, r_i]$，维护下列信息：

• 十进制数 $v_0$：在 $v_0$ 的二进制表示下，第 $j$ 位为 $1$ 当且仅当字符串的第 $j$ 为被确定为了 $0$。
• 十进制数 $v_1$：在 $v_1$ 的二进制表示下，第 $j$ 位为 $1$ 当且仅当字符串的第 $j$ 为被确定为了 $1$。

根据题目性质，线段树对 $v_0$ 和 $v_1$ 维护区间按位或和。

也就是说，对于 $\rm{push_up}$ 操作，把左右两端按位或即可，即：
$$
x.v_0=\operatorname{lson_x}.v_0\mid \operatorname{rson_x}.v_0
$$

$$
x.v_1=\operatorname{lson_x}.v_1\mid \operatorname{rson_x}.v_1
$$

void push_up(int id) {
    c[id].v0 = c[ls(id)].v0 | c[rs(id)].v0;
    c[id].v1 = c[ls(id)].v1 | c[rs(id)].v1;
}

询问

和一般的区间查询一样，但每次要包含两个返回值，与 $v_0, v_1$ 的含义相同，记录当前查询区间的信息。

还是可以用按位或合并左右两个区间。

当遇到左右区间产生矛盾时，直接 $v_0\leftarrow (-1)$ 来代表此次询问无解，向上递归时遇到 $-1$ 就不用合并区间了。

判断无解：$v_0\; \& \; v_1\neq 0$ 时无解。此时存在一个 $k$ 满足 $s[k]$ 必须为 $0$ 且 $s[k]$ 必须为 $1$，矛盾。

pair<int, int> query(int id, int l, int r, int X, int Y) {
    if(X <= l && r <= Y) {
        if(c[id].v0 & c[id].v1) return make_pair(-1, -1);
        else return make_pair(c[id].v0, c[id].v1);
    }
    int mid = (l + r) >> 1;
    pair<int, int> t1 = make_pair(0, 0), t2 = make_pair(0, 0), ret = make_pair(0, 0);
    if(X <= mid) t1 = query(ls(id), l, mid, X, Y);
    if(Y > mid) t2 = query(rs(id), mid + 1, r, X, Y);
    if(t1.first == -1 || t2.first == -1) return make_pair(-1, -1);
    ret.first = t1.first | t2.first; ret.second = t1.second | t2.second;
    if(ret.first & ret.second) return make_pair(-1, -1);
    else return ret;
}

修改

就是普通的单点修改。

void update(int id, int l, int r, int X, int w0, int w1) {
    if(l == X && r == X) {
        c[id].v0 = w0; c[id].v1 = w1;
        return ;
    }
    int mid = (l + r) >> 1;
    if(X <= mid) update(ls(id), l, mid, X, w0, w1);
    else update(rs(id), mid + 1, r, X, w0, w1);
    push_up(id);
}