UVa-11525-Permutation

出處：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2520

解題策略：segment tree，支援刪除元素與取第k大元素

排列的可能性的第∑ K i=1 Si ∗ (K − i)! 個，假設輸入以下。

4

2 1 1 0

S1 = 2，表示剩餘數字中(1,2,3,4)有兩個數字比第一個數字小，所以第一個數字為3，排列可能性為2*3!，相當於取第3大的數字。

S2 = 1，表示剩餘數字中(1,2,4)有一個數字比第二個數字小，所以第二個數字為2，排列可能性為1*2!，相當於去除第一個數字3後，取第2大的數字。

S3 = 1，表示剩餘數字中(1,4)有一個數字比第三個數字小，所以第三個數字為4，排列可能性為1*1!，相當於去除數字3與數字2後，取第2大的數字。

S4 = 0，表示剩餘數字中(1)有0個數字比第四個數字小，所以第四個數字為1，排列可能性為0*0!，相當於去除數字3與數字2與數字4後，取第1大的數字。

所以解答為3 2 4 1