https://vjudge.net/contest/311202#problem/L

之前在CF上做过类似的题,所以这次就被这种思维带过去了

后来看题解知道这题可以用到区间dp

一个排列,对每个元素给定le[i]和ri[i],表示[le[i],ri[i]]内的元素都大于等于p[i],而le[i]-1和ri[i]+1的元素都小于

p[i]

这有点像之前的CF上的线段树的题,但是可以用到区间dp,因为在区间[le,ri]内最小的元素的两边界就是le[i],ri[i]

然后就可以把一部分的元素丢到左边

得到dp[le,ri]=dp[le,minpos-1]*dp[minpos+1,ri]*C(ri-le,minpos-le);