自动搬运

查看原文

来自洛谷，原作者为

	HomuraAkemi 落日熔金，暮云合璧，人在何处

搬运于2025-08-24 22:59:43，当前版本为作者最后更新于2024-08-28 14:20:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

模拟赛搬了自己搬的题/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 酱抱抱！