「JOI Open 2024」考试 2 题解

题目大意

给定一个由 6 种规则定义的逻辑表达式（IOI 函数），它可以将 $1$ 到 $10^9$ 的整数映射为 True 或 False。规则包括：

1. [a]：判断 $x \ge a$
2. (f)：括号
3. !f：逻辑非
4. f&g：逻辑与
5. f^g：逻辑异或
6. f|g：逻辑或

优先级规则：编号大的优先，且尽量让左边的表达式更长。

给定长度为 $N$ 的表达式字符串 $S$ 和 $Q$ 个查询 $X_i$，对每个查询求表达式在 $X_i$ 处的值。

---

算法思路

1. 表达式解析

使用栈来模拟递归下降解析，处理优先级和结合性：

• 遇到 [a] 创建叶子节点
• 遇到 ! 记录取反标记
• 遇到运算符时，不断弹出栈顶元素构建子树，直到满足优先级条件
• 遇到括号时特殊处理

2. 树链剖分优化

构建表达式树后，使用树链剖分将树转化为线性序列，便于区间查询：

• hson[x] 表示重儿子
• sson[x] 表示轻儿子
• dfn[x] 表示 DFS 序
• tp[x] 表示链顶

3. 线段树维护状态转移

每个节点维护一个状态 val：

• 低位：当右子树为 0 时的结果
• 高位：当右子树为 1 时的结果

这样可以通过位运算快速合并左右子树的状态。

4. 离线处理

关键观察：当 $x$ 增加时，只有 [a] 节点会从 False 变为 True（当 $x \ge a$ 时）。因此：

• 将所有 [a] 节点按 $a$ 排序
• 将所有查询按 $X_i$ 排序
• 双指针扫描，当 $X_i \ge a$ 时更新对应节点
• 每次更新后沿树链向上传播变化

---

代码结构解析

1. 线段树结构 SegT

struct SegT {
    int val[M], pre[N];
    void build(int x, int l, int r);    // 建树
    void update(int x, int l, int v, int tl, int tr);  // 单点更新
    int query(int x, int l, int r, int tl, int tr);    // 区间查询
};

2. 主要数据结构

• ch[N][2]：左右儿子
• op[N]：节点类型（正数为 [a]，-1 为 &，-2 为 ^，-3 为 |）
• ist[N]：是否被取反
• f[N]：节点当前值

3. 核心函数

• getst()：计算节点状态
• predfs()：预处理 DFS，确定重链
• dfs()：树链剖分
• update()：更新节点值并向上传播

---

复杂度分析

• 解析：$O(N)$
• 树链剖分：$O(N)$
• 查询处理：$O((N+Q)\log N)$

由于使用了树链剖分和线段树，每次更新和查询的时间为 $O(\log^2 N)$，但实际常数较小，可以通过 $N=10^6$ 的数据。

---

关键技巧

1. 状态压缩：用 2 位表示节点的两种可能输出，支持快速合并
2. 树链剖分：将树路径查询转化为 $O(\log N)$ 个区间查询
3. 离线处理：利用 $x$ 单调性，避免重复计算
4. 栈式解析：避免递归深度过大，支持 $N=10^6$ 的表达式

---

示例

对于输入：

15 5
(![2]|[3])&![4]
1
2
3
4
5

程序会：

1. 解析表达式为树结构
2. 对查询排序：1, 2, 3, 4, 5
3. 按顺序处理，当 $x \ge 2$ 时更新 [2] 节点，当 $x \ge 3$ 时更新 [3] 节点，等等
4. 输出对应结果

---

总结

本题结合了表达式解析、树链剖分、线段树和离线处理等多种高级数据结构与算法，是一个综合性很强的题目。核心在于将表达式求值问题转化为动态树上的路径查询问题，并通过单调性优化处理大量查询。