Range LIS Query

説明は ここ に書きました。
順列:
区間:[ , )
0123456743507216[0][2][4][5][1] 011223333-101223333-2-10112223-3-2-1012223-4-3-2-101112-5-4-3-2-10112-6-5-4-3-2-1012-7-6-5-4-3-2-101-8-7-6-5-4-3-2-10(0)(1)(2)(4)(5)0011223344556677

区間 [2,5)[2, 5) に対応する subarray は (5,0,7)(5,0,7) です。LIS score は (ji)Pi,jΣ=31=2 (j-i)-P^{\Sigma}_{i, j} = 3 - 1 = 2 です。
jij-i は区間長、Pi,jΣP^{\Sigma}_{i, j} は網掛け部分の緑の丸の個数に対応します。