「2026 杭电多校 4」1005. TREE

    「2026 杭电多校 4」1005. TREE

    https://acm.hdu.edu.cn/contest/problem?cid=1232&pid=1005

    给出一个长度为 nn 的排列 a1,…,ana_1, \dots, a_n。

    有 QQ 次询问,每次询问给出两个整数 l,rl, r (1≤l≤r≤n1 \leq l \leq r \leq n),求区间 al,…,ara_l, \dots, a_r 的小根笛卡尔树的树高,定义树根的深度为 11。

    数据范围:1≤n,Q≤2×1051 \leq n, Q \leq 2\times 10^5。

    时空限制:22s / 512512MiB。

    Solution