去年调试至今: 棠梨煎雪

比利♂海灵顿 · 2021-06-29 18:34:18 · 题解

yLOI 2019 棠梨煎雪

用线段树维护两个合并规则不同的值对刚学 OI 的 MnZn 不是很友好，于是就有了这篇题解。

题意

给 m 个长 n 的 0/1 串，串中存在 ? 字符表示既可以是 0，也可以是 1。

要求支持:

单点修改

将指定串改为给出的新串。
区间查询

查询一个区间内的串共同符合的已知 0/1 串数量。换句话说，如果有 S，使得一个区间内的串在 ? 取合适字符的时候能完全匹配，求不同的 S 的数量。

n \leq 30

输出所有查询操作的 ^ 和。

思路

先思考如何高效判断 ? 不存在的时候，一个区间内的串是否一样。

因为 n 的长度很短，考虑位运算，只要一个字符串的某一位是 1，那么其它串的这一位也必须是 1，否则不匹配，如果一个字符串某一位是 0，情况也一样。

因此，我们可以用一个整数存一个串。查询的时候，查询区间 | 和，结果中的 1 的位置表示 S 中为 1 的位置。然后查询区间取 ~ 之后的 | 和，结果中 1 的位置表示 S 中为 0 的位置。

接着将两个结果取 &，如果结果不为 0，则说明 0 和 1 有冲突，不匹配，否则就匹配。

对于整数的区间 | 和，可以用 ST 表 O(1) 查询。如果需要修改，就使用线段树 O(\log n) 修改或查询。

接下来推广到 ? 存在的情况。

首先可以预见的是: 一位上状态有 3 种，一个二进制位无法表达串中一位的信息，所以很显然一个整数存这个串是不够用的。

如果一个串某一位是 ? 说明 S 中，这一位不必填 1，也不必填 0，这时用两个整数存一个串，a 的某一位为 1 表示这个位上必须填 0，b 的某一位为 1 表示这个位上必须填 1。

仍然是区间查询 | 和，将 a 和 b 的 | 和相 &，如果结果不是 0，说明这些串已知位有冲突，本次查询的答案为 0。如果结果是 0，对他们取 ~ 的结果做 &，假设结果中有 k 个位置是 1，则本次查询结果为 2^k。

实现

线段树维护整数的 | 和。

容易发现，串中每一位的位置只要一一对应，相对位置关系不影响答案，所以为了降低代码难度，我们从右往左读 (最右边的是最高位)。

因为我们建树的时候使用的是先左儿子后右儿子的顺序遍历，所以叶节点代表的点的坐标一定单调递增，所以我们可以在每次遍历到叶结点的时候读入一个串，这也算是一个小优化了吧。

代码 (缺省源已省略):

struct Node {
    unsigned Va, Vb;
    Node *LS, *RS;
} N[200100], *CntN(N - 1);
Node *Build(unsigned L, unsigned R) {
  Node *x(++CntN);
    if(L ^ R) {
    unsigned Mid((L + R)>>1);
    x->LS = Build(L, Mid);
    x->RS = Build(Mid + 1, R);
    x->Va = x->LS->Va | x->RS->Va;
    x->Vb = x->LS->Vb | x->RS->Vb;
    } else {
        while((Ch != '0') && (Ch != '1') && (Ch != '?')) Ch = getchar();
        unsigned Itmp(1);
        while((Ch == '0') || (Ch == '1') || (Ch == '?')) {
            if(Ch ^ '?') {
              if(Ch ^ '1') x->Va |= Itmp;
        else x->Vb |= Itmp;
            }
            Ch = getchar(), Itmp <<= 1;
        }
    }
    return x;
}
void Qry(Node *x, unsigned L, unsigned R) {
    if((PL <= L) && (R <= PR)) { 
      FindA |= x->Va, FindB |= x->Vb;
  } else {
    register unsigned Mid((L + R) >> 1);
    if(PR > Mid) {
      Qry(x->RS, Mid + 1, R);
    }
    if(PL <= Mid) {
      Qry(x->LS, L, Mid);
    }
  }
}
void Change(Node *x, unsigned L, unsigned R) {
    if(L ^ R) {
    unsigned Mid((L + R) >> 1);
    if(Pos <= Mid) {
      Change(x->LS, L, Mid);
    } else {
      Change(x->RS, Mid + 1, R);
    }
    x->Va = x->LS->Va | x->RS->Va;
    x->Vb = x->LS->Vb | x->RS->Vb;
  } else {
    x->Va = x->Vb = 0;
    while((Ch != '0')&&(Ch != '1')&&(Ch != '?')) Ch=getchar();
    register unsigned Itmp(1);
    while((Ch == '0')||(Ch == '1')||(Ch == '?')) {
      if(Ch ^ '?') {
        if(Ch ^ '1') x->Va |= Itmp;
        else x->Vb |= Itmp;
      }
      Ch=getchar(), Itmp <<= 1;
    }
    }
}
int main() {
    n = RD(),   m = RD(), q = RD();
    Bench = (1 << n) - 1;
    Build(1, m);
    for(register int i(1); i <= q; ++i) { 
    if(RD()) {
            Pos = RD();
      Change(N, 1, m);
        } else {
            PL = RD(), PR = RD(), FindA = FindB = 0;
      Qry(N, 1, m);
      if(!(FindA & FindB)) {
        register unsigned Tmp(((~FindA) & (~FindB)) & Bench), Cnt(1);
        while (Tmp) Cnt <<= 1, Tmp ^= LowBit(Tmp);
        Ans ^= Cnt;
      }
        }
    }
    printf("%u\n",Ans); 
    return 0;
}

树状数组

先说结论: 我们的思想不能使用树状数组。

事实上，既然是区间查询，单点修改，线段树就显得大材小用了，所以还可以尝试用树状数组做。

但是非常遗憾，因为 | 的特殊性，无法 O(1) 推算一个点的改变对区间 | 和的影响，所以很难使用树状数组维护。如果强行使用，那单次修改也需要 O(\log^2n) 的复杂度 (感性理解，~~读者自证~~，证明在后面)。

我发现题解中仍有巨佬使用树状数组过掉了此题，树状数组的做法是开 90 个树状数组，用小常数的数据结构，乘上 90 倍常数，是可以 AC 的。

分析原因，我们的线段树维护的是每一位有没有被确定是 1 或 0，但是 90 个树状数组维护的是这一个区间内有多少 1，多少 0。换句话说，我们的算法将信息进行了压缩，而压缩后的数据是树状数组所不易维护的，因为它只能通过所有子区间合并而来。合并子区间的复杂度取决于一个节点被分成了多少子区间。线段树中，一个节点分成两个子区间，而数状数组，一个节点被分成的子区间数量取决于它 LowBit 的位置，是 O(\log n) 的。这就是为什么我们合并线段树的节点的子区间更新当前节点信息需要 O(1)，但是树状数组需要 O(\log n)。因为二者的递归层数都是 O(\log n)，所以单次修改复杂度分别是 O(\log n) 和 O(\log^2n)

区间查询貌似根本就不能做，树状数组查询的是两个前缀和，要想求答案，我们需要将两个前缀和做差，因为我们不能用两个数的 |，和其中的一个数，求出另一个数。

如果我们要直接合并对应的节点，发现根本找不到对应的节点集合，谈何维护? 至于原因，是因为树状数组每一位存的是它左边 LowBit 位的和，所以对于每个右边界，都存在一个以它为右边界的节点，我们可以将右边界规定后，不断移动右边界。左边界则不同，不一定每个左边界，都存在一个以它为左边界的节点。所以就有可能找不到对应节点来合并。

结论: 用树状数组实现本题解的想法，修改 O(\log^2n)，查询 O(NO\_WAY)

历史背景

首先感谢出题人 @一扶苏一在我 OI 期间的指导，2020 年暑假，扶苏给我们出了这道题，然后我们就全军覆没了，当时机房有巨佬使用 90 棵线段树卡了过去，所以就有了题面下方修改时间的动作。

扶苏讲解之后，我调了一天，最后只有 5' (没错，就是输出 0)，这道题也成了当时学校里口口相传的毒瘤题。

因为心理阴影，我一年没有动这道题，这也成了我 尝试过的题目 中三道中的一道。主要原因是位运算对当时刚学 OI 3 年的我比较混沌，于是调题的过程变成了开奖的过程，这里把 | 改成 &，那里把 ^ 改成 |，~~大大提升了组合数学能力~~。

一年后，我终于过了此题，撒花~