Luogu7324 [WC2021] 表达式求值

题意：定义

• < 为两个数组对位取 。
• > 为两个数组对位取 。

两者的优先级相同。

给出 个长为 的数组 ，以及表达式 （只含 <、>、?、括号和编号，编号 代表数组 ）。

? 可以变成 < 和 >，每个确定的表达式可以计算出一个数列，设有 个 ?，求所有 个表达式答案的元素之和。

对 取模，，，，时限 。

---

两个数组的 可以分位考虑，于是原问题可以拆分成 个子问题，其中“数组”变为“单个数”。

观察到 非常小但 非常大，思考如何利用特殊的数据范围。

若我们将 的数改为 ，而 的数改为 ，若表达式的结果为 ，则说明 ，否则 。

有经典结论 ，于是我们只需对每个 求解上述问题。

这样，我们就把表达式转化为了 “输入 个 ，输出一个 ” 的黑盒。

---

考虑真值表思想，记 表示输入状态为 时，输出为 的方案数。这可以在表达式树上进行简单 得到。

预处理的复杂度为 。

借助 的值，我们就能快速地回答询问。

将输入的 个数 从大到小排序，分别为 。

对于 的 ，被设定为 的输入即为 ，容易求出方案数。乘以区间长度求和即为对答案的贡献。

回答询问的复杂度为 。