qoj9887

概述：给出一个长度为 $n$ 的排列 $a$ 与 $q$ 个区间 $[l_i,r_i]$，称两个区间本质不同当且仅当二者的小根笛卡尔树不同构，求这 $q$ 个区间中有几种本质不同的区间。

思路：考虑该区间笛卡尔树形式，发现其左链为从 $l$ 不断往右边比当前值小的位置跳直到跳到最小值，右链同理，除左右链外与原序列笛卡尔树结点无异。将左右链分别哈希（先对原序列笛卡尔树树哈希，再对后序链上点字符串哈希），做倍增预处理，开个 map 去重即可。