下发文件

一个子树是 BST 当且仅当该子树的中序遍历序列的点权单调不降，而每个子树的中序遍历序列是整个树中序遍历序列的一段区间。

求出中序遍历序列 $a_1, a_2, \dots, a_n$，那么设节点 $u$ 的子树对应区间 $[l, r]$，那么 $u$ 是 BST 当且仅当：

$\forall i \in [l, r), a_i \leq a_{i+1}$

方法：

• 查询某个点是否合法：只需要用树状数组维护区间中不满足 $a_i \leq a_{i+1}$ 的位置的个数。
• 修改点权：每次修改一个点的点权，只会影响该点到根路径上的节点的判断结果。并且，合法的点一定是连续的一段。
• 解决方案：使用树上倍增方法。