P8815【题解】

· · 题解

题目传送门

本题是非常经典的中缀表达式求解，让我们来逐步分析该题。

我们不妨设 S 为该表达式；mi_{l,r,k} 为 S_{l,r}（指表达式 l to r 的位置区间）中优先级第 k 低的运算符所处的下标；ma_{l,r,k} 为 S_{l,r} 中优先级第 k 高的运算符所处的下标；cnt_{l,r} 为 S_{l,r} 中运算符的数量。

对于第 1 问，想要直接求出表达式的值，我们不妨使用人脑模拟。想象一下，你现在有一个算式，运算符带有各异的优先级，那么你会如何去计算它呢？显然，正常人都会先找到 ma_{l,r,1}对应的运算符，计算完毕后，再次找到 ma_{l,r,2} 对应的运算符……以此类推。

上述是一个递归的过程。然而在计算机中，我们要反过来优先递归 mi_{l,r,1}，因为这样才能使其放在最后被计算。

具体实现方面，我们大可每次在一定区间内扫一遍，得到 mi_{l,r,1}，接着将区间以 mi_{l,r,1} 分为两部分递归（[l,mi_{l,r,1}-1]、[mi_{l,r,1}+1,r]），而这两个区间内的 mi_{l,mi_{l,r,1}-1,1} 和 mi_{mi_{l,r,1}+1,r,1} 对应的优先级一定高于 mi_{l,r,1}。当 cnt_{l,r}=0 时，说明该区间内只有一个值，直接返回。但此时 l 不一定等于 r（想一想，为什么？），所以也需要一个循环。这整个过程结束后，函数会一层层地计算，并往回跳，相当于逐步计算优先级高的运算符。

至于第 2 问的找短路数量，我们在递归下去之前判断一下就 ok 了。

在此给出 50pts 代码。

record

不出所料地 TLE 了，那么我们开始思考如何优化。

考虑到每次找 mi_{l,r,1} 都需要扫一遍区间，才导致了 \Theta(n^2) 的时间复杂度。那么有没有什么可以 \Theta(1) 查询区间最值的数据结构呢？没错，就是 st 表。

其实是我不会建后缀树qwq

这样复杂度就成功地从 \Theta(n^2) 降到了 \Theta(n\log n)。

100pts 代码

几乎是最劣解了吧

那么我们就愉快地水过了本题。