Znzryb's Blog
0%

Posted on Edited on

判断 0-based 还是 1-based，核心只看这个标号有没有实际意义：有意义就保留，没意义且只是容器访问就转成 0-based。

Posted on Edited on

题目大意

题面

给定一个长度为 nn 的整数序列 a1,a2,…,ana_1,a_2,\ldots,a_n ，一开始每个位置的值都未知。现在有 qq 次在线操作：

操作 含义
1 l r x 尝试加入约束：al⊕al+1⊕⋯⊕ar=xa_l \oplus a_{l+1} \oplus \cdots \oplus a_r = x。如果这个约束和已经采纳的约束矛盾，就丢弃；否则永久加入。
2 l r 查询 al⊕al+1⊕⋯⊕ara_l \oplus a_{l+1} \oplus \cdots \oplus a_r。如果当前约束不能唯一确定这个值，输出 -1。

样例里先把每个单点的值都约束出来：a1 = 3, a2 = 6, a3 = 7, a4 = 3, a5 = 9。

所以：

查询 结果
[1,4] 3⊕6⊕7⊕3=13 \oplus 6 \oplus 7 \oplus 3 = 1
[2,5] 6⊕7⊕3⊕9=116 \oplus 7 \oplus 3 \oplus 9 = 11
[1,5] 3⊕6⊕7⊕3⊕9=83 \oplus 6 \oplus 7 \oplus 3 \oplus 9 = 8

思路讲解

一句话

把原数组转换成前缀异或和，区间约束就变成两个前缀点之间的异或边；然后用带权并查集维护每个点到集合根的异或值，就可以在线合并约束和回答查询。

先把区间改成两个前缀点

定义前缀异或：

si=a1⊕a2⊕⋯⊕ai−1s_i = a_1 \oplus a_2 \oplus \cdots \oplus a_{i-1}

这里故意让 s1=0s_1=0，也就是 s[i] 表示第 ii 个位置之前的异或和。这样区间 [l,r] 的异或和就是：

al⊕⋯⊕ar=sl⊕sr+1a_l \oplus \cdots \oplus a_r = s_l \oplus s_{r+1}

所以操作 1 l r x 其实是在说：

1
s_l xor s_{r+1} = x

这一步很关键：原本有 nn 个未知的数组元素，转成了 n+1n+1 个前缀点之间的相对关系。所有约束都只是在连边。

关键不变量：如果两个前缀点在同一个连通块里，它们之间的异或差就已经被约束唯一确定；如果不在同一个连通块里，那它们之间还可以整体自由平移，查询答案就不能确定。

带权并查集里维护什么

普通并查集只知道两个点是不是连通；这题还需要知道连通以后它们之间的异或差。所以维护：

1
2
fa[x]      // x 的父亲
xorVal[x]  // x 到 fa[x] 的异或值

路径压缩时顺手把 xorVal[x] 改成「x 到根」的异或：

1
2
3
4
5
6
7
ll find(ll x) {
    if (fa[x] == x) return fa[x];
    ll tmp = fa[x];
    fa[x] = find(tmp);
    xorVal[x] ^= xorVal[tmp];
    return fa[x];
}

这样 find(x) 之后，xorVal[x] 就是 sx⊕sroots_x \oplus s_{\text{root}} 。如果 l 和 r+1 已经在同一个集合里，那么：

sl⊕sr+1=(sl⊕sroot)⊕(sr+1⊕sroot)s_l \oplus s_{r+1} = (s_l \oplus s_{\text{root}}) \oplus (s_{r+1} \oplus s_{\text{root}})

根的那一项异或两次会消掉，所以查询就是：

1
xorVal[l] ^ xorVal[r + 1]

合并一个新约束

现在加入约束 s_a xor s_b = val。先找到根：

1
2
ra = find(a);
rb = find(b);

如果 ra == rb，这条边没有带来新信息；它要么和已有约束一致，要么矛盾。严格写法应该检查：

1
(xorVal[a] ^ xorVal[b]) == val

这份标准代码里 ra == rb 时直接 return，因为矛盾约束被忽略后，对后续可确定的查询没有影响；不过从“判断矛盾”的语义来说，加上这个检查会更完整。

如果根不同，就把 ra 接到 rb 上，并求出 ra 到 rb 应该是多少。我们需要让合并后仍然满足：

sa⊕sb=vals_a \oplus s_b = val

因为：

sa⊕sb=(sa⊕sra)⊕(sra⊕srb)⊕(sb⊕srb)s_a \oplus s_b = (s_a \oplus s_{ra}) \oplus (s_{ra} \oplus s_{rb}) \oplus (s_b \oplus s_{rb})

所以：

1
xorVal[ra] = val ^ xorVal[a] ^ xorVal[b]

这就是代码里的核心合并式：

1
2
fa[ra] = rb;
xorVal[ra] ^= val ^ xorVal[b] ^ xorVal[a];

由于 ra 是根，原本 xorVal[ra] = 0，所以这行等价于赋值。

查询为什么会输出 -1

查询 [l,r] 时，同样先改成前缀点 l 和 r+1：

情况 说明 输出
find(l) == find(r + 1) 两个前缀点之间的异或差已经被约束系统确定 xorVal[l] ^ xorVal[r + 1]
find(l) != find(r + 1) 两个连通块之间还没有关系，答案可能随未知变量变化 -1

反正这题的本质不是“求出每个 aia_i”，而是维护前缀点之间的相对异或关系。只要相对关系能连通，答案就出来了。

复杂度

每次操作做常数次并查集 find/union，时间复杂度是 O(α(n))O(\alpha(n))，总复杂度 O((n+q)α(n))O((n+q)\alpha(n))，空间复杂度 O(n)O(n)。

AC 代码

源码较长，下面折叠保存一份标准实现。

心路历程（WA，TLE，MLE……）

这题最容易绕进去的点是想维护原数组 aia_i 的值，但其实单点值不一定能被确定。真正稳定的东西是前缀点之间的差，也就是 sl⊕sr+1s_l \oplus s_{r+1}。

还有一个实现细节：输入的 r 要立刻变成 r + 1，因为所有约束都在前缀点上连边。这个转换漏掉以后，查询会整体错一位。

附件

本页根据本地题面 PDF 和标准代码整理：/Users/zzy/Downloads/奇点蜂测序/problem.pdf、/Users/zzy/Downloads/奇点蜂测序/std.cpp。

Posted on Edited on

题目大意

有 x 张桌子，每张桌子有 s 个座位。朋友按固定顺序排队进场，Alice 对每个人只能选择安排到某张桌子，或者把他踢出派对；一旦坐下，之后不能移动。

每个人有三种性格：

  • I：只能坐在当前为空的桌子上。

  • E：只能坐在当前非空且未坐满的桌子上。

  • A：可以坐在任意未坐满的桌子上。

目标是在不改变队伍顺序的前提下，最大化最终坐下的人数。

这页只做赛时代码复盘，不展开完整题解。

思路讲解

一句话

这页不是完整题解，只记录一个赛时 WA 的方向性错误：对拍发现 I 的直接分配不够优秀之后，应该重做 I 的分配策略，而不是在错误分配后用剩下的 A 做回退回补。

补充洞见：从单向状态变化里拆角色

如果题目里有一个资源状态只发生一次单向变化，就尝试按「触发变化的人」和「变化后享受资源的人」拆角色。

这题里，桌子的状态只有一次不可逆变化：

1
空桌 -> 非空桌

所以每张桌子天然可以拆成两类位置：

角色 含义 能坐的人
starter 第一个坐下、把空桌变成非空桌的人 I / A
follower 在桌子已经非空之后坐下的人 E / A

这个抽象的重点不是换名字，而是把「桌子状态」变成「角色资源」：开一张桌本质上是消耗一个 starter 名额，并产生 s-1 个 follower 槽位。于是 A 的特殊性也变清楚了：它不是普通万能牌，而是可以在 starter / follower 两种角色之间延迟定型的弹性资源。

以后遇到类似结构，可以先问一句：资源有没有「第一次操作改变状态，后续操作享受改变后状态」这种单向过程？如果有，就优先尝试拆成「触发者 / 享受者」两类角色。

补充洞见：为什么 A 不能待定式分配

待定法只适合“候选没有过程价值”的场景；这题的 A 一旦先作为跟随者进入结构，就会产生中间过程价值，所以不能只是挂在候选池里。

这里真正要分清的，不是“要不要保留 A 的弹性”，而是 A 的弹性从哪里来。把 A 暂时记在候选池里，只能说明“以前出现过一个 A”；它还没有坐下，也没有进入任何桌子的结构。

但如果 A 先作为跟随者坐下，它就已经占过一个跟随者槽位。之后如果把这个 A 改成开桌者，它会先吐回自己原来占过的那个槽位，再额外产生新桌子的若干槽位。这个“吐回旧槽位”的能力，就是待定的 A 没有的中间过程价值。

处理方式 当前状态 以后改成开桌者时
待定的 A 只是候选，还没有进入结构 只能产生新桌子的槽位，不能吐回旧槽位
已坐下的 A 已经作为跟随者占过一个槽位 可以吐回原槽位，并产生新桌子的槽位

💡 Note: 所以 A 不能采用待定式分配：待定会丢掉它进入结构后才拥有的中间过程价值。正确的反悔不是“先不分配”，而是“先作为跟随者真实坐下，后面需要时再改成开桌者”。

这也是区分两类贪心的判断口径：如果一个候选等待期间没有过程价值，可以先挂起；如果它只有进入结构以后才会变成未来交换的支点，就必须先进入结构，再保留反悔空间。

AC 代码

AC 提交链接

心路历程（WA，TLE，MLE……）

赛时代码的错误方向

赛时代码的思路大概是先从左到右扫一遍：I 能坐空桌就直接坐，E 尽量接到已有桌子上，A 暂时存起来；后面再看剩下的 A 能不能把之前没利用好的桌子补起来。

这个方向的问题是，I 是否占用一张空桌不是一个局部收益。它会改变后面整段 A/E/I 的可行结构。一个早期 I 坐下去，看似马上多了 1，但可能把后面更有价值的“空桌开局”直接堵死。

当对拍发现“I 直接分配不够优秀”时，正确反应应该是重做 I 的选择策略；如果继续沿着旧贪心做回退，本质上是在已经丢掉的状态空间里补洞。

反例记忆

art
1
2
9 2 4
AAIAEIEEI

一种最优安排是跳过较早的 I：

坐下位置 字符 分配
0 A 第一桌第 1 人
1 A 第一桌第 2 人
3 A 第一桌第 3 人
4 E 第一桌第 4 人
5 I 第二桌第 1 人
6 E 第二桌第 2 人
7 E 第二桌第 3 人

答案是 7。

赛时代码会在位置 2 遇到 I 时立刻占掉一张空桌，于是后面再用 A 回补，也已经回不到这个方案了。

这次该记住的坑

  • 对拍其实已经指出：I 直接分配会错。

  • 赛时修偏了方向：试图通过后面的 A 回退回补，而不是重新处理 I 的分配。

  • 这个问题的本质是状态空间被前面的贪心删掉了；后处理只能在剩余状态里修，修不回被删掉的最优路径。

  • 如果对拍暴露的是“某个局部贪心决策本身不成立”，不要先想着给它补丁。先判断这个决策有没有删掉未来可能的状态；如果删掉了，就应该换状态设计。

另一种错误贪心：能开 starter 就开

这版代码的想法很直接：维护还能开的 starter 数量，以及已经开出来的 follower 槽位。遇到 I 就开 starter，遇到 A 时只要还能开 starter，也优先开 starter。

关键代码是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ll follower = 0, starter = X;
ll ans = 0;
for (int i = 0; i < N; ++i) {
    if (A[i] == 'E') {
        if (follower == 0) continue;
        --follower;
        ++ans;
    } else if (A[i] == 'I') {
        if (starter == 0) continue;
        starter--;
        follower += S - 1;
        ++ans;
    } else {
        if (follower == 0 && starter == 0) continue;
        if (starter > 0) {
            starter--;
            follower += S - 1;
            ++ans;
        } else if (follower > 0) {
            --follower;
            ++ans;
        }
    }
}

这个贪心的问题是：它把 A 过早固定成 starter 了。A 明明既可以当 starter，也可以当 follower；如果它先抢掉 starter 名额，后面的 I 就没法坐，因为 I 没有 follower 这个身份可以退。

一个很小的反例：

art
1
2
3
1
3 2 2
AAI

这份代码会这样走：

位置 字符 决策 starter follower ans
0 A 优先开 starter 1 1 1
1 A 继续优先开 starter 0 2 2
2 I 没有 starter，踢掉 0 2 2

但最优是 A 开第一桌，第二个 A 当 follower，最后的 I 再开第二桌，答案是 3。

所以这里真正要保护的不是“看到能开桌就开桌”，而是 starter 名额要尽量留给刚性的 I，A 的身份需要延迟决定。A 坐下以后不应该立刻永久绑定为 starter；它最好能作为一个可反悔的弹性资源，后面根据 E/I 的到来再决定到底补 follower 还是改成 starter。

附件

暂无。

Posted on

题目大意

给一棵 nn 个点的树和一个空集合 SS 。每一步先找到当前树上编号最大的叶子 xx ，把 xx 加入 SS ，然后可以任选另一个叶子删掉。重复 n−1n-1 次，问最后可能得到多少个不同的集合 SS 。

输入有多组测试，所有测试的 nn 之和不超过 2⋅1052\cdot 10^5 。答案对 998244353998244353 取模。

思路讲解

一句话

把树以最大编号点 nn 为根，非根点 yy 能被当前最大叶子 xx 转移到，当且仅当 need[y]<x<yneed[y] < x < y ；根节点单独处理，答案是所有能压住其它根分支的 dp[x]dp[x] 之和。

状态怎么想

集合 SS 的出现顺序一定是严格递增的一条链：当前最大叶子是 xx ，下一次进入 SS 的点只能是某个更大的 yy 。因此可以定义：

1
dp[y] = 最后一个进入 S 的点是 y 的方案数

初始状态不是 11 ，而是原树里的最大叶子：

1
2
start = max { v | degree(v) == 1 }
dp[start] = 1

这里有一个很容易错的坑：不能用“以 nn 为根后的有根树叶子”来找 start。如果根本身是原树叶子，它就是一开始的最大叶子。

非根转移

对一个非根点 yy ，设：

1
need[y] = y 的所有儿子子树里的最大编号

若当前最大叶子是 xx ，想让 yy 成为下一次最大叶子，需要先把 yy 下方所有分支删到不会冒出比 xx 更大的点。因此条件就是：

1
need[y] < x < y

所以转移可以一次性写成区间和：

1
dp[y] = sum dp[x], x in [need[y] + 1, y - 1]

这里不需要再扣掉 subtree(y)。因为如果 xx 在 yy 的子树里，那么 xx 一定被 need[y] 覆盖，和 need[y] < x 矛盾。

根节点转移

根 nn 没有父亲方向，所以不能套普通点的公式。根的每个儿子对应一条根分支，定义：

1
branchMax[v] = max(v, subTreeMx[v])

也就是这个根儿子分支里的最大编号。设所有根分支最大值里的第二大值是 secondMax。想让根成为下一次最大叶子，只需要当前 xx 压住所有其它分支：

1
x > secondMax

所以根的贡献是：

1
dp[root] = dp.query(secondMax + 1, root - 1)

注意 secondMax 是门槛，不是前驱点。不要写成查 dp[secondMax]，也不要查最大根儿子本身。

这次踩过的坑

  • start 要从原树度数为 11 的点里取最大值，不能从有根树叶子里取。

  • 维护最大值和次大值时，新最大值出现后，旧的最大值必须下放成次大值。

  • 根转移看的是第二大的根分支最大值，不是根的最大邻居，也不是最大分支的根儿子。

  • modint 不能直接用 std::max，因为模意义下比较大小没有自然语义。

  • BIT 支持 0-based 调用时，最好先把外部下标统一 normalize 到内部 1-based，再统一裁剪到 [1,n]。

Hack 例子

初始叶子如果算错，会被这组打掉：

1
2
3
4
5
6
1
5
1 3
2 4
3 4
4 5

正确答案是 1，因为最大叶子一开始就是根 5。

根转移如果只看最大邻居或最大根儿子，会被这组打掉：

1
2
3
4
5
6
7
1
6
1 4
2 6
3 5
4 5
5 6

正确答案是 2，对应集合 {3,6} 和 {3,4,6}。

1
2
3
4
5
6
7
8
6
/ \
2   5
  / \
 3   4
	/
   1

因为 3,4 都可以转移（3 可以转移的原因在下面）

1
2
// * 只要能够压制其他子树的值（mx2），那么即可向 n 转移
// * 因为可以借刀杀人，借 n 的手，把自己子树中的其他值给干掉

AC 代码

AC 提交链接

本地代码已 AC；完整源码折叠在下面。

心路历程（WA，TLE，MLE……）

  • 一开始把转移看成 x -> y 的枚举，感觉红箭头很乱；后来固定终点 yy ，发现合法前驱是一段编号区间。

  • 中途误以为还需要扣掉 subtree(y)，后来发现 need[y] < x 已经自动排除了这个情况。

  • 根节点是最容易绕的地方：普通点有父亲方向当退路，根没有，所以必须单独看根分支。

  • 真正让根变简单的是一句话：根转移只看第二大的根分支最大值。

  • 后面写代码时，几个 bug 都来自“把门槛误当成点”：secondMax 是阈值，不是要查的前驱状态。

附件

暂无。后续如果整理成完整 PDF 或动画，可以再补到这里。

Posted on Edited on

题目大意

题面

歪歪要追 T 集电视剧。对每一集，电视剧长度为 L 分钟，她预先给出 n 个可能想看的片段，第 i 个片段是闭区间 [l_i, r_i]。

她会从这些片段里选出若干个两两不重叠的片段。注意这里是闭区间，所以 [1, 3] 和 [3, 5] 算重叠，[1, 3] 和 [4, 5] 才不重叠。

同时，男明星会在这一集的 m 个时刻出现，分别是 a_i。歪歪要求每个被选择的片段里，都至少能看到一次男明星。

问在这个前提下，一集最多能看多少分钟。

输入格式

第一行输入 T。

每组数据先输入 L, n, m。

接下来 n 行输入 l_i, r_i。

最后一行输入 m 个 a_i。

数据范围

  • T <= 10

  • L <= 1e9

  • n, m <= 1e5

  • 1 <= a_i <= L

  • 1 <= l_i <= r_i <= L

样例

1
2
3
4
5
6
7
8
9
10
11
2
10 5 3
1 2
3 3
1 6
4 10
8 10
1 3 10
10 1 5
6 10
1 2 3 4 5

输出：

1
2
10
0

思路讲解

一句话

先用二分筛掉“不含明星出现时刻”的片段，剩下的问题就是经典的带权区间选择：每个合法区间的权重是长度，按右端点排序后做 DP。

第一步：判断一个片段能不能看

把所有明星出现时刻 a_i 排序。对片段 [l, r]，用 lower_bound(a, l) 找到第一个 >= l 的出现时刻。

如果这个位置存在，并且值 <= r，说明片段里至少出现了一次男明星，这个片段可以进入后面的 DP。

这个筛选是 O(log m) 的，所以 n 个片段总共 O(n log m)。

第二步：把问题看成带权区间选择

筛完以后，每个片段都有一个权重：

w=r−l+1w = r - l + 1

现在要从这些区间里选若干个互不重叠的区间，让权重和最大。

闭区间的边界非常关键：前一个区间的右端点必须严格小于当前区间左端点，也就是 r_prev < l_now。

按右端点从小到大排序。设 dp[i] 表示只考虑前 i 个合法区间时，最多能看的分钟数。

对当前区间 [l_i, r_i]，有两种选择：

  • 不选它：答案是 dp[i - 1]

  • 选它：找到最后一个满足 r_j < l_i 的区间 j，答案是 dp[j] + w_i

于是转移就是：

dp[i]=max(dp[i−1],dp[j]+wi)dp[i] = max(dp[i - 1], dp[j] + w_i)

这里 j 可以用 lower_bound(right, l_i) - 1 找到。

第三步：为什么要考虑“单独选当前区间”

这题最容易挂的地方不是大方向，而是这个小分支。

如果当前区间前面没有任何能接上的前驱，也就是 lower_bound(right, l_i) 指向开头，它仍然可以单独选。

所以当前区间的贡献至少应该参与一次比较：

1
dp[i] = max(dp[i - 1], lr[i].w);

然后如果存在前驱，再尝试：

1
dp[i] = max(dp[i], dp[j] + lr[i].w);

反例很小：

1
2
3
4
5
1
100 2 2
1 5
2 100
1 2

两个区间都合法，但互相重叠。最优应该单独选 [2, 100]，答案是 99。若没有“单独选当前区间”这个分支，就会错误地保留 [1, 5]，输出 5。

复杂度

排序明星出现时刻、排序区间，再对每个片段二分一次。

总复杂度 O((n + m) log n)，空间 O(n + m)。

AC 代码

AC 提交链接

源码较长，折叠放在下面。

心路历程（WA，TLE，MLE……）

  • 一开始 DP 大方向是对的：合法片段筛选 + 按右端点排序 + 找前驱。

  • 坑点出在当前区间没有前驱的时候，代码直接 continue，漏掉了“当前区间单独作为答案”的情况。

  • 修法是先执行 dp[i] = max(dp[i - 1], lr[i].w)，再在存在前驱时尝试拼上前驱。

  • 这类带权区间 DP 可以记一句话：当前区间要么不选，要么自己开一段，要么接在一个合法前驱后面。

附件

暂无额外附件。