1 条题解

  • 0
    @ 2026-4-23 17:05:25

    这是由 AI 翻译为中文文本的官方题解，由于官方题解过长，不保证 AI 翻译一定准确无误，请批判性阅读。

    Step 0：问题概要

    0 问题概要

    • 有 NN 张瓷砖，每张瓷砖的正反两面颜色为白或黑。
    • 正面、背面颜色信息由字符串 S,TS, T 给出。
    • 可以进行“把 2 张瓷砖合并成 1 张瓷砖”的操作。

    0 问题概要：合并规则

    • 可以由瓷砖 a,ba, b 生成瓷砖 cc。
    • 若 aa 的背面颜色与 bb 的正面颜色相同，则 cc 的正面为黑；否则为白。
    • 若 aa 的正面颜色与 bb 的背面颜色相同，则 cc 的背面为黑；否则为白。

    0 问题概要：查询

    • 需要处理 QQ 个查询。
    • 查询分为“修改查询”和“判定查询”。
    • 修改查询：把某一张瓷砖替换为另一张瓷砖。
    • 判定查询：取出区间 [L,R][L, R] 的瓷砖按顺序排列，反复进行上述合并操作，判断是否能使“正面为白色的瓷砖数量”变为 MM 张。
    • 本质上是：对 S,TS, T 的某个区间进行判定。
    • 对于 S,TS, T 的某个 RANGE（区间）……
    • STRANGE（原文如此保留）

    0 约束

    • N≤300000N \le 300000
    • Q≤300000Q \le 300000
    • 瓷砖颜色与区间没有特殊限制。

    0 小任务（Subtask）

    小任务编号 / NN / QQ / 查询类型 / 分值

    • 1：66 / 66 分
    • 2：100100 / 仅判定 / 1010 分
    • 3：500500 / 仅判定 / 99 分
    • 4：17001700 / 仅判定 / 88 分
    • 5：1000010000 / 1000010000 / 2323 分
    • 6：100000100000 / 100000100000 / 1414 分
    • 7：无额外限制 / 3030 分

    Subtask 1：N≤6N \le 6

    1 全搜索

    • 瓷砖的颜色状态有 44 种。
    • 长度为 nn 的序列状态共有 4n=22n4^n = 2^{2n} 种。
    • 当 n≤6n \le 6 时，这不超过 40964096。
    • 能不能把所有状态都枚举出来？
    • 可以。
    • 可以视作：点数为 O(4N)O(4^N)、边数为 O(N4N)O(N4^N) 的有向图可达性判定等问题。

    1 转化为图

    • 构建一个表示状态转移的图。
    • 希望把瓷砖序列的状态编码成数字。
    • 将其解释为 44 进制，或 55 进制（用某个数字表示“没有卡片/瓷砖”）会更方便。
    • 无论哪种方式，都能在 O(N4N)O(N4^N) 内建图。
    • 预处理：先求出所有顶点之间的可达性。
    • 用 DFS 或 BFS 等喜欢的方法即可。

    1 转化为图：复杂度与提示

    • 有了它，查询可用 O(1)O(1) 左右回答。
    • 总复杂度例如 O(N42N+Q)O(N4^{2N} + Q) 等。
    • 常数因子还可以进一步降低，所以只要实现别太糟糕，应该能过。
    • 参考后面两页的实现技巧。
    • 如果实在 TLE，可以按“对应状态中瓷砖数量”分层把图拆开等。
    • 但这可能比小任务 2 的实现更难，所以不太建议。

    1 另一种解法

    • 在判定查询中，合并顺序的选择有 O((N−1)!)O((N-1)!) 种。
    • 全部尝试即可。
    • 复杂度例如 O((N−1)!⋅Q)O((N-1)! \cdot Q)。
    • 特别地：若同一组“从状态 ss 出发，想把正面为白的数量变为 mm”的组合 (s,m)(s, m) 出现两次以上，后面就可以偷懒跳过，这是可行的加速。
    • 这叫“记忆化递归”。

    1 实现技巧

    • 上述解法都需要维护“瓷砖状态序列”。
    • 想把每张瓷砖的状态对应到 00 到 33 的 44 个整数。
    • 但要怎么对应？
    • 使用 $2 \times (\text{正面黑为 }0,\ \text{正面白为 }1) + 1 \times (\text{背面黑为 }0,\ \text{背面白为 }1)$ 这种表示会很方便。

    1 进一步思考

    • 继续使用上面的 0∼30 \sim 3 表示法来理解合并操作。
    • cc 的正面：若 aa 的背面与 bb 的正面相同则为黑，否则为白。
    • cc 的背面：若 aa 的正面与 bb 的背面相同则为黑，否则为白。
    • 以该表示法改写：
      • cc 的正面颜色是 aa 的背面颜色与 bb 的正面颜色的 XOR。
      • cc 的背面颜色是 aa 的正面颜色与 bb 的背面颜色的 XOR。
    • XOR 指“按位异或/排他的累积和”。
    • 在本题的约束下，可以理解为“做加法再对 22 取模”也没问题。

    1 后续约定

    • 从这里开始，把黑对应为 00，白对应为 11。
    • cc 的正面 = aa 的背面 XOR bb 的正面。
    • cc 的背面 = aa 的正面 XOR bb 的背面。

    1 表记法说明

    • 之后若写成 “#-@” 这种形式，请理解为：正面是 “#”、背面是 “@” 的瓷砖。
    • 例如 “1-0” 表示：正面白、背面黑的瓷砖。
    • “*” 表示 0,10, 1 任意都可以。
    • 例如 “0-*” 表示：正面黑，背面任意都 OK 的瓷砖。
    • 判定查询就是：请判断能否把 “1-*” 的数量变为 MM 张。

    Subtask 2：N≤100N \le 100，仅判定查询

    2 仅判定查询

    • 先把所有可能的判定查询答案都预处理出来。
    • 定义 dp[i][j][k]dp[i][j][k]：能否把区间 [i,j)[i, j) 变成含有 kk 张 “1-*” 的状态？
    • 这是典型的区间 DP。
    • 但在推转移时，若要把区间变成 1 张瓷砖会遇到困难。
    • 因此再做一个辅助的区间 DP。
    • 定义 dp′[i][j][k]dp'[i][j][k]：能否把区间 [i,j)[i, j) 变成“对应于 kk 的那种瓷砖”共 1 张？

    2 DP 复杂度

    • dp′[i][j][k]dp'[i][j][k]：可以用例如 O(N3)O(N^3) 的复杂度求出。
    • dp[i][j][k]dp[i][j][k]：有了 dp′dp' 后，可以用例如 O(N4)O(N^4) 的复杂度求出。
    • 总体为 O(N4+Q)O(N^4 + Q)。

    Subtask 3：N≤500N \le 500，仅判定查询

    3 前言

    • 在小任务 2 中使用了区间 DP。
    • 方针保持不变。
    • 加速思路有两个：
      • 一种是通用的加速手段；
      • 另一种是利用本题特有性质的加速手段。
    • 实现其中 1 个就能过小任务 3；两个都实现应该能过小任务 4。
    • 也会很依赖常数因子。

    3 前言：先讲通用加速

    • 下面先介绍“通用的加速手段”。

    3 DP 定义回顾

    • 回顾 DP 定义：
      • dp′[i][j][k]dp'[i][j][k]：区间 [i,j)[i, j) 能否变成对应 kk 的 1 张瓷砖？
      • dp[i][j][k]dp[i][j][k]：区间 [i,j)[i, j) 能否变成含 kk 张 “1-*”？
    • 这两者都是“能否”的形式，也就是布尔值（true/false）。

    3 bitset 加速

    • 这种布尔 DP 往往可以用 bitset 加速。
    • 设机器字长为 ww，复杂度通常能获得 1/w1/w 的量级加速。
    • 一般 w=64w = 64。
    • 使用 bitset 后可变为 O(N4/w+Q)O(N^4 / w + Q)。

    Subtask 4：N≤1700N \le 1700，仅判定查询

    4 前言

    • 加速思路有两个：
      • 通用手段；
      • 本题特有性质。
    • 这里介绍“利用本题特有性质”的那一种。

    4 思考

    • 如果能解本题的判定查询，似乎也能求 “1-*” 的最大值与最小值。
    • 先考虑最大化。
    • 首先：一次合并操作会让 “1-*” 的数量变化多少？

    4 关注差分

    • “减少”的可能是 −2-2、−1-1。
    • “增加”的可能是 +1+1。
    • 因此差分落在 −2-2 到 +1+1 之间。

    4 性质 01

    • 性质 01：
      • 在“当前值”和“最大值”之间的所有整数值都可以取到。
    • 可以证明上述性质成立。
    • 证明中会用到引理：“差分在 −2-2 到 +1+1 之间”。
    • 数学比较强的人，可能会联想到“介值定理”的感觉。

    4 证明 01

    • 性质 01：当前值与最大值之间全部可取。
    • 证明：
      • 使用引理“差分在 −2-2 到 +1+1 之间”。
      • 设当前 “1-” 数为 xx，取一条使 “1-” 最大化的操作序列。
      • 设最终结果为 x′x'（x≤x′x \le x'）。
      • 假设存在某个 zz 满足 x<z<x′x < z < x'，但无法达到 zz 张。
      • 那么必然存在某一步操作使得 “1-*” 的数量从 ≤z−1\le z-1 一次跳到 ≥z+1\ge z+1。
      • 这与引理矛盾，因此性质成立。

    4 最大化

    • 当前值很好求（用前缀和之类随便什么都行）。
    • 下面求最大值。
    • 首先，起初已经是 “1-*” 的瓷砖不用动也没关系。
    • 把瓷砖序列划分成若干区间，把每个区间压成 1 张瓷砖来理解：
      • 含有 “1-” 的区间，最多只能得到 1 张 “1-”。
      • 而这 1 张在初始时就已经达成了，所以把这些区间直接移除、只在剩余部分操作不会吃亏。

    4 最大化：只剩 0-* 区间

    • 剩下的是仅由 “0-*” 瓷砖构成的区间的最大化问题。
    • 每张瓷砖只可能是 “0-0” 或 “0-1”。

    4 最大化：块结构

    • 可以把序列看成许多块的排列，每块形如：
      • [ [0−1×n]+[0−0×m] ][\ [0-1 \times n] + [0-0 \times m]\ ]
    • 其中 n,mn, m 为非负。
    • 若认为“把 0-0 放到左边”的操作没有意义，则自然会得到这样的顺序。

    4 最大化：每块的最大值

    • 对每个块，其最大值为 $\left\lfloor \dfrac{n + \min(m, 1)}{2} \right\rfloor$。
    • 从左到右每次取 2 张合并即可实现。

    4 最大化：块之间不需要跨越

    • 实际上整体最大值就是各块最大值之和。
    • 因为如果跨块合并，就会变成用 “0-0” 和 “0-1” 去合并，而这没有意义。
    • 也可以用关于长度的归纳法证明。

    4 最大化：结论与转向最小化

    • 总之，最大值可以在 O(N)O(N) 求出。
    • 最大化看起来问题不大。
    • 接着考虑最小化。

    4 走向最小化

    • 观察之前的区间 DP 表，会发现大多数位置都是 true。

    4 最小化：现象

    • 反过来，那些不是 true 的情况，看起来会出现 true/false 交替的模式。
    • 观察“不太 true 的情况”，几乎都是 “0-0” 或 “1-1”。
    • “比较 true 的情况”里，似乎 33 以上都能做出来。
    • 事实上确实如此。
    • 下面证明。

    4 关注第一步操作

    • 先看第一步能做什么：
      • 1-0 + 0-* => 0-*
      • 1-0 + 1-* => 1-*
      • 0-1 + 1-* => 0-*
      • 0-1 + 0-* => 1-*
    • 这些操作会让 “1-*” 的数量增加或减少 11。
    • 上面 3 个是 −1-1，下面 1 个是 +1+1。

    4 若这些操作都做不了

    • 如果这些操作都做不了，那么只要存在 0-1、1-0，它们必然只能出现在最右端。
    • “无法进行上述操作”这一性质在操作后仍会保持。
    • 在这种情况下，“1-*” 的数量的奇偶性保持不变，且只能每次减少 22。
    • 下面改为假设：上述操作中至少有一种可以做。

    4 取出可操作的两张

    • 取出能进行上述某种操作的那两张瓷砖。
    • 序列可写为：左侧 LL +（这两张）+ 右侧 RR。
    • 设左侧能达到的最小值为 mLm_L，右侧能达到的最小值为 mRm_R。
    • 这里二者都不超过 11（把各自区间一直合并到剩 1 张即可）。
    • 设在 LL、中间两张、RR 中，“1-*” 的数量分别为 nL,nM,nRn_L, n_M, n_R。

    4 若第一步能做到 -1

    • （1）若第一步能做出 −1-1 的操作：
      • 不先合并中间两张，可以得到从 nL+nM+nRn_L + n_M + n_R 到 mL+nM+mRm_L + n_M + m_R 的一条操作序列。
      • 若先做这一步，则可得到从 nL+nM+nR−1n_L + n_M + n_R - 1 到 mL+nM+mR−1m_L + n_M + m_R - 1 的一条操作序列。
      • 结合“差分在 −2-2 到 −1-1”之间，可知从 mL+nM+mR−1m_L + n_M + m_R - 1 到 nL+nM+nRn_L + n_M + n_R 的所有值都能构造出来。
    • 证明：反证法。
    • 且有 mL+nM+mR−1≤1+2+1−1=3m_L + n_M + m_R - 1 \le 1 + 2 + 1 - 1 = 3。

    4 若第一步能做到 +1

    • （2）若第一步能做出 +1+1 的操作：
      • 与（1）同样思路可得：从 mL+nM+mRm_L + n_M + m_R 到 nL+nM+nRn_L + n_M + n_R 的所有值都能构造出来。
    • 证明：反证法。
    • 且有 mL+nM+mR≤1+0+1=2m_L + n_M + m_R \le 1 + 0 + 1 = 2。

    4 结论：只需关心 0..2

    • 总之，只要能做到 −1-1 或 +1+1，就可以构造出 33 及以上。
    • 因此对
      • dp[i][j][k]dp[i][j][k]：区间 [i,j)[i, j) 能否把 “1-*” 做到 kk 张？
      • 这个 kk 只需要考虑 0≤k≤20 \le k \le 2 即可。
    • 这样就能降低 DP 的计算量。
    • 例如总体可做到 O(N3/w+Q)O(N^3 / w + Q)。
    • 仅靠这一条，在 O(N3+Q)O(N^3 + Q) 下就能过小任务 3。

    Subtask 5：N≤1000, Q≤1000N \le 1000,\ Q \le 1000

    5 回顾

    • 区间能构造的最大值可在 O(N)O(N) 求出。
    • “减少”的部分，变成了判断能否构造出 0,1,20, 1, 2。
    • 希望进一步把这些判定加速。

    5 实验

    • 继续像之前一样做实验。
    • 会发现一些规律。
    • 文中 “oo 不能做” 的意思是：无法通过某种操作使 “1-*” 的数量变成 oo 张。

    5 性质 02

    • 性质 02：
      • “无法做到 0”的充要条件是：0-1、1-0 除了最右边 2 张以外都不存在。

    5 性质 02：证明

    • 把序列分成若干区间，每个区间最终都变成 1 张瓷砖，并希望它们全部都是 “0-*” 的形态。
    • 除去最右边 2 张后，只依赖于 1-1 的数量奇偶性。
    • 若左侧的 1-1 为偶数，则归约到最右边 2 张。
    • （左侧 1-1 为偶数的情况下）
      • 可行： [0-0, 0-]、[0-1, -]、[1-0, 0-]、[1-1, 1-*]
      • 不可行：其他情况（otherwise）
    • 若左侧的 1-1 为奇数，则归约到 “1-1 与最右边 2 张”。
      • 可行：1-1 +（[0-0, 1-]、[0-1, 0-]、[1-0, -]、[1-1, 0-*]）
      • 不可行：其他情况（otherwise）

    5 性质 03

    • 性质 03：
      • “无法做到 1”的充要条件是：
        • （特性 1）1-* 的数量为偶数，且
        • 1-0、0-1 除了右端以外都不存在。

    5 性质 03：证明（归纳）

    • 用关于长度的归纳法。长度为 1 时显然。
    • 先证明：满足上述特性的序列，经过一步操作后仍满足。
    • 序列可写为： [0-0 或 1-1] ×(L−1)\times (L-1) + [-]。
    • 若合并不涉及 -，则显然保持。
    • 即便涉及 -，也可以通过分类讨论证明保持。

    5 性质 03：证明（反方向）

    • 再证明：不满足上述特性的序列，总能让一步后仍不满足，或者能构造出 1。
    • 若在右 2 张以外存在 0-1、1-0，则可行，因此假设不存在。
    • 则序列可写为： [0-0 或 1-1] ×(L−2)\times (L-2) + [0-1 或 1-0] + [-]。

    情况（1）：倒数第二张是 0-1

    • （1-i）设 L−2L-2 部分中 1-1 的数量为偶数：
      • 若最右端是 0-*，先合并右 2 张即可。
      • 若最右端是 1-，把 L−2L-2 全部做成 0-0，则可做出 1-。
    • （1-ii）设 L−2L-2 部分中 1-1 的数量为奇数：
      • 若最右端是 0-*，把除最右端外的部分合并成 1-0 即可。
      • 若最右端是 1-，把 L−2L-2 合并后变成 1-，再把右 2 张合并变成 0-*，因此可行。

    情况（2）：倒数第二张是 1-0

    • （2-i）设 L−2L-2 部分中 1-1 的数量为偶数：
      • 若最右端是 0-*，把除最右端外的部分合并成 1-0 即可。
      • 若最右端是 1-，把全部合并即可得到 1-。
    • （2-ii）设 L−2L-2 部分中 1-1 的数量为奇数：
      • 若最右端是 0-*，合并右 2 张即可。
      • 若最右端是 1-*，把除最右端外合并成 0-1 即可。

    归纳收束

    • 综合讨论可知只需考虑： [0-0, 1-1] ×(L−1)\times (L-1) + [-]。
    • 若 1-* 为奇数：合并右 2 张即可。
    • 若 1-* 为偶数：与假设矛盾。
    • 因此归纳成立。

    5 性质 04

    • 性质 04：
      • “无法做到 2”的充要条件是：
        -（原文一处表述）可做的最大值为 2，且
        • 1-* 为奇数，且
        • 0-1 除了右端以外都不存在。

    5 性质 04（修正表述）与证明

    • 性质 04：
      • “无法做到 2”的充要条件是：
        • 可做的最大值小于 2，且
        • 1-* 为奇数，且
        • 0-1 除了右端以外都不存在。
    • 证明：
      • 若最大值 ≤2\le 2，则显然：最大值为 0 或 1 时不可能；为 2 时显然可以。
      • 以下讨论最大值 ≥3\ge 3 的情况，并把讨论限制在（1-* 为奇数）且（0-1 除了右端以外都不存在）。
      • 当（1-* 为奇数）且（0-1 除了右端以外都不存在）时，序列可写为： [0-0 或 1-1] ×(L−1)\times (L-1) + [0-1 或 1-1]。
      • 因为 1-* 的奇偶性不变，所以结论成立。
      • 接着考虑不满足上述条件的情况：
        • 若当前 1-* 数 ≤2\le 2，在朝最大值推进的过程中就会出现 2。
        • 令当前 1-* 数 ≥3\ge 3。
        • 若某连续子串包含 [0-1, 0-] 或 [0-1, 1-]，则可以构造 2。
        • 只需分别考虑“不碰这两张”的操作序列与“先碰这两张”的操作序列即可（与小任务 4 的“关注第一步”同思路）。
      • 若不存在 [0-1, 0-] 或 [0-1, 1-] 这样的连续子串，则序列会呈现类似：
        • [1-] ×?\times ?、[0-0] ×?\times ?、[1-] ×?\times ?、……、[0-1] ×(0 or 1)\times (0 \text{ or } 1) 的块结构。
      • （1）不存在 1-0 的情况：
        • 1-* 只剩 1-1，1-* 的奇偶性成为不变量，因此成立。
      • （2）存在 1-0 的情况：
        • 再按是否存在 0-1 分类。
        • （2-i）存在 0-1：
          • 若 1-0 在右端以外出现，则能构造 2；且 0-1 比“在右端”更有利。
        • （2-ii）不存在 0-1：
          • 考虑 1-0 只在右端出现的情况：序列为 [0-0 或 1-1] ×(L−1)\times (L-1) + [1-0]。
          • 这时 1-* 的奇偶性是不变量，因此成立。

    5 解法总结

    • 判断 0-1、1-0 若存在是否只能在右端，也可以在 O(N)O(N) 完成。
    • 判断能否做到 0,1,20, 1, 2 都能在 O(N)O(N) 完成。
    • 最大值也能在 O(N)O(N) 求出。
    • 因此每个查询可在 O(N)O(N) 解决。
    • 总体为 O(NQ)O(NQ)，可以通过。

    Subtask 7：无额外限制（满分任务）

    7 回顾

    • 若常数因子不好或语言较慢，可能只能做到小任务 6。
    • 这里作为小任务 7，说明满分做法。
    • 回顾小任务 5：
      • 判断 0-1、1-0 若存在是否只能在右端：O(N)O(N)。
      • 判断能否做到 0,1,20, 1, 2：O(N)O(N)。
      • 判断最大值：O(N)O(N)。

    7 走向 Segment Tree

    • 其实上述这些都能放到 Segment Tree（线段树）上。

    7 解法：把“右端性”放进线段树

    • “0-1、1-0 若存在是否只能在右端”的判定：
      • 只需要知道区间内 0-0、0-1、1-0、1-1 各有多少个即可。
      • 于是就是“一点更新 / 区间和”的 Segment Tree。
      • 可以建 4 棵树，也可以把 4 个计数打包成一个幺半群（monoid）信息。
      • 若携带 4 个信息，用 array 实现常数会更好。
    • “能否做到 0, 1, 2”的判定也能用这棵树完成。

    7 解法：最大值的线段树信息

    • 最大值按块计算，因此希望维护“块的信息”。
    • 设计合并（ACL 的 op）时，需要以下信息：
      • 包含左端的块的信息；
      • 包含右端的块的信息；
      • 当前区间是否恰好只有 1 个块。
    • 之后用这些信息努力实现合并即可（实现会比较重）。

    7 解法：复杂度

    • 最终可用 Segment Tree 处理所有内容。
    • 因为有两类线段树，先做抽象会更易实现。
    • 在 AtCoder 环境可用 ACL（AtCoder Library），会更省事。
    • 即使不能抽象，能“手写出来”在 final 也会很有用。
    • 需要的内容：
      • 0-1、1-0 若存在是否只能在右端；
      • 能否做到 0,1,20, 1, 2；
      • 最大值。
    • 这些都能放到 Segment Tree 上：
      • 可用 O(log⁡N)O(\log N) 做单点修改与区间积（区间合并）。
      • 总体复杂度 O(N+Qlog⁡N)O(N + Q\log N)。
    • 顺带一提：若 0-1、1-0 在右端以外存在，则 1、2 必然可做，因此实现时只需关心 0 即可。

    源码：

    ## Step 0：问题概要

### 0 问题概要
- 有 $N$ 张瓷砖，每张瓷砖的正反两面颜色为白或黑。  
- 正面、背面颜色信息由字符串 $S, T$ 给出。  
- 可以进行“把 2 张瓷砖合并成 1 张瓷砖”的操作。  

### 0 问题概要：合并规则
- 可以由瓷砖 $a, b$ 生成瓷砖 $c$。  
- 若 $a$ 的背面颜色与 $b$ 的正面颜色相同，则 $c$ 的正面为黑；否则为白。  
- 若 $a$ 的正面颜色与 $b$ 的背面颜色相同，则 $c$ 的背面为黑；否则为白。  

### 0 问题概要：查询
- 需要处理 $Q$ 个查询。  
- 查询分为“修改查询”和“判定查询”。  
- 修改查询：把某一张瓷砖替换为另一张瓷砖。  
- 判定查询：取出区间 $[L, R]$ 的瓷砖按顺序排列，反复进行上述合并操作，判断是否能使“正面为白色的瓷砖数量”变为 $M$ 张。  
- 本质上是：对 $S, T$ 的某个区间进行判定。  
- 对于 $S, T$ 的某个 RANGE（区间）……  
- STRANGE（原文如此保留）

### 0 约束
- $N \le 300000$  
- $Q \le 300000$  
- 瓷砖颜色与区间没有特殊限制。  

### 0 小任务（Subtask）
小任务编号 / $N$ / $Q$ / 查询类型 / 分值
- 1：$6$ / $6$ 分  
- 2：$100$ / 仅判定 / $10$ 分  
- 3：$500$ / 仅判定 / $9$ 分  
- 4：$1700$ / 仅判定 / $8$ 分  
- 5：$10000$ / $10000$ / $23$ 分  
- 6：$100000$ / $100000$ / $14$ 分  
- 7：无额外限制 / $30$ 分  

---

## Subtask 1：$N \le 6$

### 1 全搜索
- 瓷砖的颜色状态有 $4$ 种。  
- 长度为 $n$ 的序列状态共有 $4^n = 2^{2n}$ 种。  
- 当 $n \le 6$ 时，这不超过 $4096$。  
- 能不能把所有状态都枚举出来？  
- 可以。  
- 可以视作：点数为 $O(4^N)$、边数为 $O(N4^N)$ 的有向图可达性判定等问题。  

### 1 转化为图
- 构建一个表示状态转移的图。  
- 希望把瓷砖序列的状态编码成数字。  
- 将其解释为 $4$ 进制，或 $5$ 进制（用某个数字表示“没有卡片/瓷砖”）会更方便。  
- 无论哪种方式，都能在 $O(N4^N)$ 内建图。  
- 预处理：先求出所有顶点之间的可达性。  
- 用 DFS 或 BFS 等喜欢的方法即可。  

### 1 转化为图：复杂度与提示
- 有了它，查询可用 $O(1)$ 左右回答。  
- 总复杂度例如 $O(N4^{2N} + Q)$ 等。  
- 常数因子还可以进一步降低，所以只要实现别太糟糕，应该能过。  
- 参考后面两页的实现技巧。  
- 如果实在 TLE，可以按“对应状态中瓷砖数量”分层把图拆开等。  
- 但这可能比小任务 2 的实现更难，所以不太建议。  

### 1 另一种解法
- 在判定查询中，合并顺序的选择有 $O((N-1)!)$ 种。  
- 全部尝试即可。  
- 复杂度例如 $O((N-1)! \cdot Q)$。  
- 特别地：若同一组“从状态 $s$ 出发，想把正面为白的数量变为 $m$”的组合 $(s, m)$ 出现两次以上，后面就可以偷懒跳过，这是可行的加速。  
- 这叫“记忆化递归”。  

### 1 实现技巧
- 上述解法都需要维护“瓷砖状态序列”。  
- 想把每张瓷砖的状态对应到 $0$ 到 $3$ 的 $4$ 个整数。  
- 但要怎么对应？  
- 使用 $2 \times (\text{正面黑为 }0,\ \text{正面白为 }1) + 1 \times (\text{背面黑为 }0,\ \text{背面白为 }1)$ 这种表示会很方便。  

### 1 进一步思考
- 继续使用上面的 $0 \sim 3$ 表示法来理解合并操作。  
- $c$ 的正面：若 $a$ 的背面与 $b$ 的正面相同则为黑，否则为白。  
- $c$ 的背面：若 $a$ 的正面与 $b$ 的背面相同则为黑，否则为白。  
- 以该表示法改写：  
  - $c$ 的正面颜色是 $a$ 的背面颜色与 $b$ 的正面颜色的 XOR。  
  - $c$ 的背面颜色是 $a$ 的正面颜色与 $b$ 的背面颜色的 XOR。  
- XOR 指“按位异或/排他的累积和”。  
- 在本题的约束下，可以理解为“做加法再对 $2$ 取模”也没问题。  

### 1 后续约定
- 从这里开始，把黑对应为 $0$，白对应为 $1$。  
- $c$ 的正面 = $a$ 的背面 XOR $b$ 的正面。  
- $c$ 的背面 = $a$ 的正面 XOR $b$ 的背面。  

### 1 表记法说明
- 之后若写成 “#-@” 这种形式，请理解为：正面是 “#”、背面是 “@” 的瓷砖。  
- 例如 “1-0” 表示：正面白、背面黑的瓷砖。  
- “*” 表示 $0, 1$ 任意都可以。  
- 例如 “0-*” 表示：正面黑，背面任意都 OK 的瓷砖。  
- 判定查询就是：请判断能否把 “1-*” 的数量变为 $M$ 张。  

---

## Subtask 2：$N \le 100$，仅判定查询

### 2 仅判定查询
- 先把所有可能的判定查询答案都预处理出来。  
- 定义 $dp[i][j][k]$：能否把区间 $[i, j)$ 变成含有 $k$ 张 “1-*” 的状态？  
- 这是典型的区间 DP。  
- 但在推转移时，若要把区间变成 1 张瓷砖会遇到困难。  
- 因此再做一个辅助的区间 DP。  
- 定义 $dp'[i][j][k]$：能否把区间 $[i, j)$ 变成“对应于 $k$ 的那种瓷砖”共 1 张？  

### 2 DP 复杂度
- $dp'[i][j][k]$：可以用例如 $O(N^3)$ 的复杂度求出。  
- $dp[i][j][k]$：有了 $dp'$ 后，可以用例如 $O(N^4)$ 的复杂度求出。  
- 总体为 $O(N^4 + Q)$。  

---

## Subtask 3：$N \le 500$，仅判定查询

### 3 前言
- 在小任务 2 中使用了区间 DP。  
- 方针保持不变。  
- 加速思路有两个：  
  - 一种是通用的加速手段；  
  - 另一种是利用本题特有性质的加速手段。  
- 实现其中 1 个就能过小任务 3；两个都实现应该能过小任务 4。  
- 也会很依赖常数因子。  

### 3 前言：先讲通用加速
- 下面先介绍“通用的加速手段”。  

### 3 DP 定义回顾
- 回顾 DP 定义：  
  - $dp'[i][j][k]$：区间 $[i, j)$ 能否变成对应 $k$ 的 1 张瓷砖？  
  - $dp[i][j][k]$：区间 $[i, j)$ 能否变成含 $k$ 张 “1-*”？  
- 这两者都是“能否”的形式，也就是布尔值（true/false）。  

### 3 bitset 加速
- 这种布尔 DP 往往可以用 bitset 加速。  
- 设机器字长为 $w$，复杂度通常能获得 $1/w$ 的量级加速。  
- 一般 $w = 64$。  
- 使用 bitset 后可变为 $O(N^4 / w + Q)$。  

---

## Subtask 4：$N \le 1700$，仅判定查询

### 4 前言
- 加速思路有两个：  
  - 通用手段；  
  - 本题特有性质。  
- 这里介绍“利用本题特有性质”的那一种。  

### 4 思考
- 如果能解本题的判定查询，似乎也能求 “1-*” 的最大值与最小值。  
- 先考虑最大化。  
- 首先：一次合并操作会让 “1-*” 的数量变化多少？  

### 4 关注差分
- “减少”的可能是 $-2$、$-1$。  
- “增加”的可能是 $+1$。  
- 因此差分落在 $-2$ 到 $+1$ 之间。  

### 4 性质 01
- 性质 01：  
  - 在“当前值”和“最大值”之间的所有整数值都可以取到。  
- 可以证明上述性质成立。  
- 证明中会用到引理：“差分在 $-2$ 到 $+1$ 之间”。  
- 数学比较强的人，可能会联想到“介值定理”的感觉。  

### 4 证明 01
- 性质 01：当前值与最大值之间全部可取。  
- 证明：  
  - 使用引理“差分在 $-2$ 到 $+1$ 之间”。  
  - 设当前 “1-*” 数为 $x$，取一条使 “1-*” 最大化的操作序列。  
  - 设最终结果为 $x'$（$x \le x'$）。  
  - 假设存在某个 $z$ 满足 $x < z < x'$，但无法达到 $z$ 张。  
  - 那么必然存在某一步操作使得 “1-*” 的数量从 $\le z-1$ 一次跳到 $\ge z+1$。  
  - 这与引理矛盾，因此性质成立。  

### 4 最大化
- 当前值很好求（用前缀和之类随便什么都行）。  
- 下面求最大值。  
- 首先，起初已经是 “1-*” 的瓷砖不用动也没关系。  
- 把瓷砖序列划分成若干区间，把每个区间压成 1 张瓷砖来理解：  
  - 含有 “1-*” 的区间，最多只能得到 1 张 “1-*”。  
  - 而这 1 张在初始时就已经达成了，所以把这些区间直接移除、只在剩余部分操作不会吃亏。  

### 4 最大化：只剩 0-* 区间
- 剩下的是仅由 “0-*” 瓷砖构成的区间的最大化问题。  
- 每张瓷砖只可能是 “0-0” 或 “0-1”。  

### 4 最大化：块结构
- 可以把序列看成许多块的排列，每块形如：  
  - $[\ [0-1 \times n] + [0-0 \times m]\ ]$  
- 其中 $n, m$ 为非负。  
- 若认为“把 0-0 放到左边”的操作没有意义，则自然会得到这样的顺序。  

### 4 最大化：每块的最大值
- 对每个块，其最大值为 $\left\lfloor \dfrac{n + \min(m, 1)}{2} \right\rfloor$。  
- 从左到右每次取 2 张合并即可实现。  

### 4 最大化：块之间不需要跨越
- 实际上整体最大值就是各块最大值之和。  
- 因为如果跨块合并，就会变成用 “0-0” 和 “0-1” 去合并，而这没有意义。  
- 也可以用关于长度的归纳法证明。  

### 4 最大化：结论与转向最小化
- 总之，最大值可以在 $O(N)$ 求出。  
- 最大化看起来问题不大。  
- 接着考虑最小化。  

### 4 走向最小化
- 观察之前的区间 DP 表，会发现大多数位置都是 true。  

### 4 最小化：现象
- 反过来，那些不是 true 的情况，看起来会出现 true/false 交替的模式。  
- 观察“不太 true 的情况”，几乎都是 “0-0” 或 “1-1”。  
- “比较 true 的情况”里，似乎 $3$ 以上都能做出来。  
- 事实上确实如此。  
- 下面证明。  

### 4 关注第一步操作
- 先看第一步能做什么：  
  - 1-0 + 0-* => 0-*  
  - 1-0 + 1-* => 1-*  
  - 0-1 + 1-* => 0-*  
  - 0-1 + 0-* => 1-*  
- 这些操作会让 “1-*” 的数量增加或减少 $1$。  
- 上面 3 个是 $-1$，下面 1 个是 $+1$。  

### 4 若这些操作都做不了
- 如果这些操作都做不了，那么只要存在 0-1、1-0，它们必然只能出现在最右端。  
- “无法进行上述操作”这一性质在操作后仍会保持。  
- 在这种情况下，“1-*” 的数量的奇偶性保持不变，且只能每次减少 $2$。  
- 下面改为假设：上述操作中至少有一种可以做。  

### 4 取出可操作的两张
- 取出能进行上述某种操作的那两张瓷砖。  
- 序列可写为：左侧 $L$ +（这两张）+ 右侧 $R$。  
- 设左侧能达到的最小值为 $m_L$，右侧能达到的最小值为 $m_R$。  
- 这里二者都不超过 $1$（把各自区间一直合并到剩 1 张即可）。  
- 设在 $L$、中间两张、$R$ 中，“1-*” 的数量分别为 $n_L, n_M, n_R$。  

### 4 若第一步能做到 -1
- （1）若第一步能做出 $-1$ 的操作：  
  - 不先合并中间两张，可以得到从 $n_L + n_M + n_R$ 到 $m_L + n_M + m_R$ 的一条操作序列。  
  - 若先做这一步，则可得到从 $n_L + n_M + n_R - 1$ 到 $m_L + n_M + m_R - 1$ 的一条操作序列。  
  - 结合“差分在 $-2$ 到 $-1$”之间，可知从 $m_L + n_M + m_R - 1$ 到 $n_L + n_M + n_R$ 的所有值都能构造出来。  
- 证明：反证法。  
- 且有 $m_L + n_M + m_R - 1 \le 1 + 2 + 1 - 1 = 3$。  

### 4 若第一步能做到 +1
- （2）若第一步能做出 $+1$ 的操作：  
  - 与（1）同样思路可得：从 $m_L + n_M + m_R$ 到 $n_L + n_M + n_R$ 的所有值都能构造出来。  
- 证明：反证法。  
- 且有 $m_L + n_M + m_R \le 1 + 0 + 1 = 2$。  

### 4 结论：只需关心 0..2
- 总之，只要能做到 $-1$ 或 $+1$，就可以构造出 $3$ 及以上。  
- 因此对  
  - $dp[i][j][k]$：区间 $[i, j)$ 能否把 “1-*” 做到 $k$ 张？  
  - 这个 $k$ 只需要考虑 $0 \le k \le 2$ 即可。  
- 这样就能降低 DP 的计算量。  
- 例如总体可做到 $O(N^3 / w + Q)$。  
- 仅靠这一条，在 $O(N^3 + Q)$ 下就能过小任务 3。  

---

## Subtask 5：$N \le 1000,\ Q \le 1000$

### 5 回顾
- 区间能构造的最大值可在 $O(N)$ 求出。  
- “减少”的部分，变成了判断能否构造出 $0, 1, 2$。  
- 希望进一步把这些判定加速。  

### 5 实验
- 继续像之前一样做实验。  
- 会发现一些规律。  
- 文中 “oo 不能做” 的意思是：无法通过某种操作使 “1-*” 的数量变成 oo 张。  

### 5 性质 02
- 性质 02：  
  - “无法做到 0”的充要条件是：0-1、1-0 除了最右边 2 张以外都不存在。  

### 5 性质 02：证明
- 把序列分成若干区间，每个区间最终都变成 1 张瓷砖，并希望它们全部都是 “0-*” 的形态。  
- 除去最右边 2 张后，只依赖于 1-1 的数量奇偶性。  
- 若左侧的 1-1 为偶数，则归约到最右边 2 张。  
- （左侧 1-1 为偶数的情况下）  
  - 可行： [0-0, 0-*]、[0-1, *-*]、[1-0, 0-*]、[1-1, 1-*]  
  - 不可行：其他情况（otherwise）  
- 若左侧的 1-1 为奇数，则归约到 “1-1 与最右边 2 张”。  
  - 可行：1-1 +（[0-0, 1-*]、[0-1, 0-*]、[1-0, *-*]、[1-1, 0-*]）  
  - 不可行：其他情况（otherwise）  

### 5 性质 03
- 性质 03：  
  - “无法做到 1”的充要条件是：  
    - （特性 1）1-* 的数量为偶数，且  
    - 1-0、0-1 除了右端以外都不存在。  

### 5 性质 03：证明（归纳）
- 用关于长度的归纳法。长度为 1 时显然。  
- 先证明：满足上述特性的序列，经过一步操作后仍满足。  
- 序列可写为： [0-0 或 1-1] $\times (L-1)$ + [*-*]。  
- 若合并不涉及 *-*，则显然保持。  
- 即便涉及 *-*，也可以通过分类讨论证明保持。  

### 5 性质 03：证明（反方向）
- 再证明：不满足上述特性的序列，总能让一步后仍不满足，或者能构造出 1。  
- 若在右 2 张以外存在 0-1、1-0，则可行，因此假设不存在。  
- 则序列可写为： [0-0 或 1-1] $\times (L-2)$ + [0-1 或 1-0] + [*-*]。  

#### 情况（1）：倒数第二张是 0-1
- （1-i）设 $L-2$ 部分中 1-1 的数量为偶数：  
  - 若最右端是 0-*，先合并右 2 张即可。  
  - 若最右端是 1-*，把 $L-2$ 全部做成 0-0，则可做出 1-*。  
- （1-ii）设 $L-2$ 部分中 1-1 的数量为奇数：  
  - 若最右端是 0-*，把除最右端外的部分合并成 1-0 即可。  
  - 若最右端是 1-*，把 $L-2$ 合并后变成 1-*，再把右 2 张合并变成 0-*，因此可行。  

#### 情况（2）：倒数第二张是 1-0
- （2-i）设 $L-2$ 部分中 1-1 的数量为偶数：  
  - 若最右端是 0-*，把除最右端外的部分合并成 1-0 即可。  
  - 若最右端是 1-*，把全部合并即可得到 1-*。  
- （2-ii）设 $L-2$ 部分中 1-1 的数量为奇数：  
  - 若最右端是 0-*，合并右 2 张即可。  
  - 若最右端是 1-*，把除最右端外合并成 0-1 即可。  

#### 归纳收束
- 综合讨论可知只需考虑： [0-0, 1-1] $\times (L-1)$ + [*-*]。  
- 若 1-* 为奇数：合并右 2 张即可。  
- 若 1-* 为偶数：与假设矛盾。  
- 因此归纳成立。  

### 5 性质 04
- 性质 04：  
  - “无法做到 2”的充要条件是：  
    -（原文一处表述）可做的最大值为 2，且  
    - 1-* 为奇数，且  
    - 0-1 除了右端以外都不存在。  

### 5 性质 04（修正表述）与证明
- 性质 04：  
  - “无法做到 2”的充要条件是：  
    - 可做的最大值小于 2，且  
    - 1-* 为奇数，且  
    - 0-1 除了右端以外都不存在。  
- 证明：  
  - 若最大值 $\le 2$，则显然：最大值为 0 或 1 时不可能；为 2 时显然可以。  
  - 以下讨论最大值 $\ge 3$ 的情况，并把讨论限制在（1-* 为奇数）且（0-1 除了右端以外都不存在）。  
  - 当（1-* 为奇数）且（0-1 除了右端以外都不存在）时，序列可写为： [0-0 或 1-1] $\times (L-1)$ + [0-1 或 1-1]。  
  - 因为 1-* 的奇偶性不变，所以结论成立。  
  - 接着考虑不满足上述条件的情况：  
    - 若当前 1-* 数 $\le 2$，在朝最大值推进的过程中就会出现 2。  
    - 令当前 1-* 数 $\ge 3$。  
    - 若某连续子串包含 [0-1, 0-*] 或 [0-1, 1-*]，则可以构造 2。  
    - 只需分别考虑“不碰这两张”的操作序列与“先碰这两张”的操作序列即可（与小任务 4 的“关注第一步”同思路）。  
  - 若不存在 [0-1, 0-*] 或 [0-1, 1-*] 这样的连续子串，则序列会呈现类似：  
    - [1-*] $\times ?$、[0-0] $\times ?$、[1-*] $\times ?$、……、[0-1] $\times (0 \text{ or } 1)$ 的块结构。  
  - （1）不存在 1-0 的情况：  
    - 1-* 只剩 1-1，1-* 的奇偶性成为不变量，因此成立。  
  - （2）存在 1-0 的情况：  
    - 再按是否存在 0-1 分类。  
    - （2-i）存在 0-1：  
      - 若 1-0 在右端以外出现，则能构造 2；且 0-1 比“在右端”更有利。  
    - （2-ii）不存在 0-1：  
      - 考虑 1-0 只在右端出现的情况：序列为 [0-0 或 1-1] $\times (L-1)$ + [1-0]。  
      - 这时 1-* 的奇偶性是不变量，因此成立。  

### 5 解法总结
- 判断 0-1、1-0 若存在是否只能在右端，也可以在 $O(N)$ 完成。  
- 判断能否做到 $0, 1, 2$ 都能在 $O(N)$ 完成。  
- 最大值也能在 $O(N)$ 求出。  
- 因此每个查询可在 $O(N)$ 解决。  
- 总体为 $O(NQ)$，可以通过。  

---

## Subtask 7：无额外限制（满分任务）

### 7 回顾
- 若常数因子不好或语言较慢，可能只能做到小任务 6。  
- 这里作为小任务 7，说明满分做法。  
- 回顾小任务 5：  
  - 判断 0-1、1-0 若存在是否只能在右端：$O(N)$。  
  - 判断能否做到 $0, 1, 2$：$O(N)$。  
  - 判断最大值：$O(N)$。  

### 7 走向 Segment Tree
- 其实上述这些都能放到 Segment Tree（线段树）上。  

### 7 解法：把“右端性”放进线段树
- “0-1、1-0 若存在是否只能在右端”的判定：  
  - 只需要知道区间内 0-0、0-1、1-0、1-1 各有多少个即可。  
  - 于是就是“一点更新 / 区间和”的 Segment Tree。  
  - 可以建 4 棵树，也可以把 4 个计数打包成一个幺半群（monoid）信息。  
  - 若携带 4 个信息，用 array 实现常数会更好。  
- “能否做到 0, 1, 2”的判定也能用这棵树完成。  

### 7 解法：最大值的线段树信息
- 最大值按块计算，因此希望维护“块的信息”。  
- 设计合并（ACL 的 op）时，需要以下信息：  
  - 包含左端的块的信息；  
  - 包含右端的块的信息；  
  - 当前区间是否恰好只有 1 个块。  
- 之后用这些信息努力实现合并即可（实现会比较重）。  

### 7 解法：复杂度
- 最终可用 Segment Tree 处理所有内容。  
- 因为有两类线段树，先做抽象会更易实现。  
- 在 AtCoder 环境可用 ACL（AtCoder Library），会更省事。  
- 即使不能抽象，能“手写出来”在 final 也会很有用。  
- 需要的内容：  
  - 0-1、1-0 若存在是否只能在右端；  
  - 能否做到 $0, 1, 2$；  
  - 最大值。  
- 这些都能放到 Segment Tree 上：  
  - 可用 $O(\log N)$ 做单点修改与区间积（区间合并）。  
  - 总体复杂度 $O(N + Q\log N)$。  
- 顺带一提：若 0-1、1-0 在右端以外存在，则 1、2 必然可做，因此实现时只需关心 0 即可。

    官方提供的示例代码：

    #include <array>
#include <iostream>
#include <vector>
using namespace std;

using P = pair<int, int>;
using vi = array<int, 4>;

template< typename S, S (*op)(S, S), S (*e)() >
struct segmenttree{
    private:
    int _n;
    vector<S> node;

    public:
    segmenttree() = default;

    segmenttree(vector<S> &v){
        int n = v.size();
        _n = 1;
        while(_n < n){
            _n *= 2;
        }
        node.resize(2 * _n, e());
        for(int i = 0; i < n; i++){
            node[i + _n] = v[i];
        }
        for(int i = _n - 1; i >= 0; i--){
            node[i] = op(node[2 * i], node[2 * i + 1]);
        }
    }

    void set(int i, S val){
        i += _n;
        node[i] = val;
        while(i > 1){
            i >>= 1;
            node[i] = op(node[2 * i], node[2 * i + 1]);
        }
    }

    S get(int i){
        i += _n;
        return node[i];
    }

    S prod(int l, int r){
        S pdl = e(), pdr = e();
        l += _n, r += _n;

        while(l < r){
            if(l & 1){
                pdl = op(pdl, node[l++]);
            }
            if(r & 1){
                pdr = op(node[--r], pdr);
            }
            l >>= 1;
            r >>= 1;
        }

        return op(pdl, pdr);
    }
};

struct S{
    int len;
    int max_white;
    P left;
    P right;
};

int f(int n, int m){
    return (n + min(m, 1)) / 2;
}

pair<P, P> merge(P &left, P &right){
    auto [n1, m1] = left;
    auto [n2, m2] = right;
    if(m1 == 0 || n2 == 0){
        return {{n1 + n2, m1 + m2}, {n1 + n2, m1 + m2}};
    }
    return {left, right};
}

S op_S(S a, S b){
    S res;
    res.len = a.len + b.len;
    res.max_white = a.max_white + b.max_white;
    if(a.right.second == 0 || b.left.first == 0){
        auto [n1, m1] = a.right;
        auto [n2, m2] = b.left;
        res.max_white -= f(n1, m1);
        res.max_white -= f(n2, m2);
        res.max_white += f(n1 + n2, m1 + m2);
    }
    if(a.left.first + a.left.second == a.len){
        res.left = merge(a.left, b.left).first;
    }
    else{
        res.left = a.left;
    }
    if(b.right.first + b.right.second == b.len){
        res.right = merge(a.right, b.right).second;
    }
    else{
        res.right = b.right;
    }
    return res;
}

S e_S(){
    return {0, 0, {0, 0}, {0, 0}};
}

S state(char f, char b){
    if(f == 'W'){
        return {1, 1, {0, 0}, {0, 0}};
    }
    else{
        if(b == 'B'){
            return {1, 0, {0, 1}, {0, 1}};
        }
        else{
            return {1, 0, {1, 0}, {1, 0}};
        }
    }

    cerr << "Error in state()";
    return e_S();
}

vi op_vi(vi a, vi b){
    vi res;
    for(int i = 0; i < 4; i++){
        res[i] = a[i] + b[i];
    }
    return res;
}

vi e_vi(){
    return {0, 0, 0, 0};
}

int id(char f, char b){
    int res = 0;
    if(f == 'W'){
        res += 2;
    }
    if(b == 'W'){
        res += 1;
    }
    return res;
}

bool make_zero(int l, int r, string &s, string & t, segmenttree<vi, op_vi, e_vi> &seg_vi){
    if(r - l == 1){
        return 1 - (s[l] == 'W');
    }
    if(r - l == 2){
        if(s[l] == 'B' && s[l + 1] == 'B'){
            return 1;
        }
        return (t[l] == s[l + 1]);
    }

    int a = 0;
    vi v = seg_vi.prod(l, r - 2);
    if(v[1] > 0 || v[2] > 0){
        return 1;
    }
    a = (v[2] + v[3]) % 2;

    if(a == 0){
        if(s[r - 2] == 'B' && s[r - 1] == 'B'){
            return 1;
        }
        return (t[r - 2] == s[r - 1]);
    }

    if(t[r - 2] == 'B'){
        if(s[r - 2] == 'B'){
            return 1 - (s[r - 1] == 'B');
        }
        else{
            return 1;
        }
    }
    else{
        return 1 - (s[r - 1] == 'W');
    }

    cerr << "Error in make_zero()" << endl;
    return 0;
}

bool make_one(int l, int r, string &s, string & t, segmenttree<vi, op_vi, e_vi> &seg_vi){
    int a = 0;
    vi v = seg_vi.prod(l, r - 1);
    if(v[1] > 0 || v[2] > 0){
        return 1;
    }
    a = (v[2] + v[3] + (s[r - 1] == 'W')) % 2;
    return a;
}

bool make_two(int l, int r, string &s, string & t, segmenttree<vi, op_vi, e_vi> &seg_vi){
    int a = 1;
    vi v = seg_vi.prod(l, r - 1);
    if(v[1] > 0 || v[2] > 0){
        return 1;
    }
    a = (v[2] + v[3] + (s[r - 1] == 'W')) % 2;
    return a;
}

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

    int n;
    string s, t;
    cin >> n >> s >> t;

    vector<S> card(n);
    vector<vi> count(n);
    for(int i = 0; i < n; i++){
        card[i] = state(s[i], t[i]);
        count[i][id(s[i], t[i])] += 1;
    }

    segmenttree<S, op_S, e_S> seg_S(card);
    segmenttree<vi, op_vi, e_vi> seg_vi(count);

    int q;
    cin >> q;

    while(q--){
        int p;
        cin >> p;

        if(p == 1){
            int x;
            char y, z;
            cin >> x >> y >> z;

            x--;
            s[x] = y;
            t[x] = z;
            seg_S.set(x, state(y, z));

            vi c = e_vi();
            c[id(y, z)] += 1;
            count[x] = c;
            seg_vi.set(x, c);
        }
        else{
            int l, r, m;
            cin >> l >> r >> m;
            
            l--;

            int mx = seg_S.prod(l, r).max_white;
            if(mx < m){
                cout << "No\n";
                continue;
            }

            vi c = seg_vi.prod(l, r);
            int now_white = c[2] + c[3];
            if(now_white <= m){
                cout << "Yes\n";
                continue;
            }

            // m < now_white
            vi rightmost = seg_vi.get(r - 1);

            if(c[1] + c[2] == rightmost[1] + rightmost[2]){
                if((now_white - m) % 2 == 0){
                    cout << "Yes\n";
                }
                else{
                    cout << "No\n";
                }
                continue;
            }

            if(m == 0){
                if(make_zero(l, r, s, t, seg_vi)){
                    cout << "Yes\n";
                }
                else{
                    cout << "No\n";
                }
            }
            else if(m == 1){
                if(make_one(l, r, s, t, seg_vi)){
                    cout << "Yes\n";
                }
                else{
                    cout << "No\n";
                }
            }
            else if(m == 2){
                if(make_two(l, r, s, t, seg_vi)){
                    cout << "Yes\n";
                }
                else{
                    cout << "No\n";
                }
            }
            else{
                cout << "Yes\n";
            }
        }
    }
}
    • 1

    「JOI 2026 Semifinal」奇妙的机器

    信息

    ID
    9659
    时间
    2000ms
    内存
    1024MiB
    难度
    10
    标签
    递交数
    3
    已通过
    1
    上传者
    1. Language
    2. 兼容模式
    3. 主题
    3. Worker 0, 17ms
    4. Powered by Hydro v5.0.1 Community