qoj9887

居然有个高手 · 2024-12-19 18:40:23 · 个人记录

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

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