题解 P5067 【[Ynoi2014]长存不灭的过去，逐渐消逝的未来】
SSerxhs
·
·
题解
题外话：
谢 lxl 邀
应该是这个系列最后一道没有题解的了。
顺便把 comeintopower 的代码叉了，四舍五入算一血了
题意：给定一个表达式，要求 O(k\log n) 支持单点修改、区间求值，其中 k 是原表达式括号层数。
前置知识 1：表达式求值-表达式树解法（无括号）
众所周知，表达式求值有两种求法，用栈存储和建立表达式树。栈存储显然不能支持任何修改操作，考虑表达式树。
表达式树是把表达式拆成一棵树，且满足运算优先级越高深度越大。数字也属于运算符，且优先级是最高的（即连接其他数字）。
表达式树的求值方法是合并两个子树，对当前节点代表的是数字/运算符分类讨论合并。以下记 s_x 表示以 x 为根的子树的值。
这里 \texttt* 的权值为 2\times 7=14，\texttt3 的权值为 431，\texttt + 的权值为 431+14=445。
容易看出，若节点为数字则权值为 s_x=10^{siz_r}\times (10\times s_l+v_x)+s_{r}，若节点为乘号则权值为 s_x=s_l\times s_r，若节点为加号则权值为 s_x=s_l+s_r。
为什么？因为我们总是先合并优先级较高的，所以不会导致先加后乘。同时加、乘、数结合都有结合律，不需要考虑顺序的问题。
数结合大量使用 10^x，先线性预处理可以规避一个不必要的 \log。
等会，好像漏了减号？
这是错误的。考虑如下情形
计算结果为 $s_{\texttt{+}}=9,s_\texttt{-}=0$，显然不符合实际情况。
能否通过调整减号优先级来规避？
也是不可以的。本质是是减号和加减号都不具有结合律。
考虑对于**加减号**节点同时维护**左值**和**右值**，左值表示左边有减号就会变号的部分，右值表示不会变号的部分，分别记为 $s_{x,0},s_{x,1}$，那么加号的转移显然是 $s_{x,0}=s_{l,0}$，$s_{x,1}=s_{l,1}+s_{r,0}+s_{r,1}$，而减号的转移为 $s_{x,0}=s_{l,0}$，$s_{x,1}=s_{l,1}-s_{r,0}+s_{r,1}$。
对于乘号和数字节点，只有左值没有右值，转移不变。
这样我们就实现了对加减乘三种运算在表达式树上的维护。
至于无解的情况，当且仅当子节点无解或运算符左右某一子节点为空节点。
### 前置知识 2：fhq-treap
优先级越高深度越大，这让我们想到 treap 作为 tree+heap 同时满足平衡树和小根堆的良好性质，同时用 fhq-treap 维护序列可以支持序列操作提取区间。具体地，在 fhq-treap 的 `merge` 过程中，可以在比较随机值大小前先比较符号的类型使优先级越高的节点深度越大。一种更方便的实现方式是在随机值中加入符号的权重。
~~没错，以上只是本题前置知识。~~
以下是本题正片。
#### subtask 0：没有修改，没有括号。
用 fhq-treap 提取出查询区间，直接输出根节点的值即可。
#### subtask 1：只有修改，没有括号。
由于修改是单点修改，修改对应节点即可。
然而修改节点可能需要修改随机值（因为可能改变了符号类型），所以必须先 `split` 出这个点，再 `merge` 成原树，而不能修改后暴力 `pushup`。其他部分不变。
#### subtask 2：只有括号，没有对括号的修改，也不会修改成括号。
括号显然不能用简单的优先级表示。括号是成对作用的，这提示我们直接维护整对括号。考虑新设定一种**三叉**节点表示一对括号，其左右儿子含义和其他节点相同，**中儿子**表示括号内序列。
注意原表达式并不是括号匹配的，需要在表达式左右加上若干括号使得表达式括号匹配。
考虑括号节点的权值。由定义知括号的优先级比任意运算符高，而其与数字优先级关系对答案没有影响，可以直接设定括号优先级与数字相同。
除了以下提到的问题以外修改和前面没有任何区别，不再赘述。
区间查询开始变得辣手起来。由于 fhq-treap 需要 `split`，但括号节点总要维护完整的一对括号，显然是不能裂开的。
注意到如果 $l$ 和 $r$ 在同一对括号的内外侧，表达式一定不合法。这种情况可以特判掉。
那么剩下的辣手情况就是 $l,r$ 都在要裂开的括号里面。可以考虑直接不裂括号，强行进入中儿子递归计算。
好像有哪里不太对的？
$l,r$ 还可以在括号上。
具体地，对于 $l$ 在右括号的情况，一定不合法。
对于 $l$ 在左括号的情况，$r$ 必定在右括号或其右侧（否则不合法）。这时提取整个区间即可。
对于 $r$ 在括号上的情况，同理讨论。
于是我们解决了这个 subtask。
注意及时 `pushup`。这里有很多节点需要 `pushup`。
#### subtask 3：最终版
多了一个操作：对括号的修改。
首先，删去一个括号等价于先增加一个括号和它匹配，再把要删去的括号成对删去。删去这一步非常容易，只需要把同一括号下的另外两棵子树 `merge` 即可，基本等价于增加一个括号。
增加一个括号，首先显然要在极远处增加另一个括号保持匹配。但增加意味着打乱了原本的括号匹配关系。
例如 $\texttt{a(b\red(cd\blue(e\blue)f\red)g)h}$，若在 $\texttt{cd}$ 之间新增括号 $\texttt{\green(}$，意味着括号变为 $\texttt{a(b\red(c\green(d\blue(e\blue)f\red)g)h\green)}$，蓝色没有影响，但红色和黑色的括号匹配都变了。
可以注意到，增添括号影响了包含这一点的所有括号，需要把 $\texttt c$ 取出来，在上一层进行合并，同时也要继续取出 $\texttt b$，可以递归实现。
这里说起来比较简单，但是实现起来十分繁琐。注意不要直接把左右儿子赋值，这里维护的是 fhq-treap，所有的操作都必须通过 `merge` 和 `split` 进行，否则会导致小根堆性质不满足。在一般题目中小规模不满足小根堆性质仅仅会导致常数差异（因为几乎无法卡掉），但在此题会直接导致 WA，此题不失为一道锻炼 fhq-treap 的好题。
于是你终于写完了代码，交了一发上去
TLE/MLE on test 51
~~没错，我的 hack 数据~~
题面仅仅保证了原串的括号层数，但我们一顿操作之后层数早已不是初始的层数。
优化：若外面连续两层都是仅有括号，可以直接压缩。
优化后可以通过。
~~于是你就解决了这个系列码量最大的题目~~
