魔法师塔子哥手上有一个长度为 n 的序列 a1,a2,…,an,保证序列里每个元素不重复且1<=a[i]<=n,他想要知道有多少个区间 [l,r] 满足区间内部的数 al,al+1,…,ar 能够构成一个排列。
为了更好地掌握魔法,塔子哥需要知道所有满足条件的区间数量。现在他请你来帮助他计算这个数量。
排列其实就是一个数组n个数,包好1到n各一位。所以我们可以将数组排序,将数组排序后,我们会得到一个1到n的数组,同时我们用pos[i]表示一个数i在原数组的位置。
我们拿样例[2,1,5,3,4]来讲解。
那么我们得到的pos数组是[2,1,4,5,3]。
我们将数字和pos绑定为二元组。所以原数组为[(2,1),(1,2),(5,3),(3,4),(4,5)](二元组第一位表示数字,第二位表示位置)。我们排序后,数组变为[(1,2),(2,1),(3,4),(4,5),(5,3)]。
扫码备注加群即可,期待您的到来~