【洛谷-P5522】[yLOI2019] 棠梨煎雪 • TonyYin's Blog

题目地址：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;
}

cpp

询问#

和一般的区间查询一样，但每次要包含两个返回值，与 $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;
}

cpp

修改#

就是普通的单点修改。

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);
}

cpp

代码#

#include <bits/stdc++.h>
using namespace std;
const int MAXM = 1e5 + 10;
struct Point{
    int v0; //v0[i]=1 表示：二进制下的第i位确定为 0
    int v1; //v1[i]=1 表示：二进制下的第i位确定为 1
} c[MAXM << 2];
int n, m, q;
int v0[MAXM], v1[MAXM];
int lc[MAXM << 2], rc[MAXM << 2];
namespace Segment_Tree{
    #define ls(x) (x << 1)
    #define rs(x) (x << 1 | 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;
    }
    void build(int id, int l, int r) {
        lc[id] = l; rc[id] = r;
        if(l == r) {
            c[id] = (Point){v0[l], v1[l]};
            return ;
        }
        int mid = (l + r) >> 1;
        build(ls(id), l, mid);
        build(rs(id), mid + 1, r);
        push_up(id);
    }
    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);
    }
    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;
    }
};
using namespace Segment_Tree;
string in;
int main() {
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= m; i++) {
        cin >> in;
        for(int j = 0; j < n; j++) {
            v0[i] <<= 1; v1[i] <<= 1;
            if(in[j] == '0') v0[i] |= 1;
            if(in[j] == '1') v1[i] |= 1;
        }
    }
    build(1, 1, m);
    int ans = 0;
    while(q--) {
        int opt; scanf("%d", &opt);
        if(opt == 0) {
            int l, r; scanf("%d%d", &l, &r);
            pair<int, int> ret = query(1, 1, m, l, r); 
            if(ret.first == -1) continue;
            int tmp = ret.first | ret.second, cnt = 0;
            for(int i = 0; i < n; i++) if((tmp & (1 << i)) == 0) cnt++;
            ans ^= (1 << cnt); 
        } else {
            int pos, w0 = 0, w1 = 0; cin >> pos >> in;
            for(int i = 0; i < n; i++) {
                w0 <<= 1; w1 <<= 1;
                if(in[i] == '0') w0 |= 1;
                if(in[i] == '1') w1 |= 1;
            }
            update(1, 1, m, pos, w0, w1);
        }
    }
    cout << ans << endl;
    return 0;
}

cpp