Luogu – P5522 – [yLOI2019] 棠梨煎雪

题目地址: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);
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
window.pjaxLoaded = function(){ } window.pjaxLoaded();