Madoka 酱抱抱！ | 【题解】P10626 [JOI Open 2024] 考试 2

· · 题解

模拟赛搬了自己搬的题/jy

一句话概括解法：建出表达式树后扫描线动态 DP 即可。

建出表达式树

可能方法比较笨。

首先用栈可以算出每个 !|^& 对应的深度，对每个符号每个深度开一个数组记录下标。\operatorname{build}(l,r) 时，按照优先级二分找出运算符位置即可。这样是 \Theta(n\log n) 的。

动态 DP

从小到大扫描询问，每个节点的值只会变化一次。所以时间复杂度是对的。

我们对于每个节点，维护一个函数 f:\{0,1\}\to \{0,1\}。

套路地，对于叶子，就是 \{0,1\}\to \{0\}/\{1\}。对于非叶子，在进行重链剖分时分类讨论：根据轻儿子的状态和当前节点的类型来确定 f 的具体映射。例如当前节点是 \texttt{or}，轻儿子是 \texttt{False}，那么显然有：f(x)=x。然后用你喜欢的数据结构维护即可，查询就是查询一条重链函数的复合（f\circ g）。

根据实现的不同，是 \Theta((n+q)\log^2 n) 或者 \Theta((n+q)\log n) 的。

Madoka 酱抱抱！