P8528 [Ynoi2003] 铃原露露


给定一棵有根树，顶点编号为 $1,2,\dots,n$，对 $2\le i\le n$ 有 $f_{i}$ 为 $i$ 的父亲。$a_1,\dots,a_n$ 是 $1,\dots,n$ 的排列。 共 $m$ 次询问，每次询问给出 $l,r$，询问有多少个二元组 $L,R$，满足 $l\le L\le R\le r$，且对任意 $L\le a_x\le a_y\le R$，有 $x,y$ 在树上的最近公共祖先 $z$ 满足 $L\le a_z\le R$。 以上所有数值为整数。

无

无

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078 对于 $100\%$ 的数据，满足 $1\le n,m\le 2\times 10^5$，$1\le f_i\le i-1$，$l\le r$。 对于 $25\%$ 的数据，满足 $n,m\le 100$。 对于另外 $25\%$ 的数据，满足 $n,m\le 3000$。 对于另外 $25\%$ 的数据，满足 $l=1,\;r=n,\;m=1$。 对于另外 $25\%$ 的数据，无特殊限制。