8. 看著數列的卦長

0 Judge

Code: 0


看著數列的卦長

題目敘述

sprout
ㄠㄨ

卦長對數列有莫名的喜愛,他常常盯著數列發呆,數著SMM數對的各數。對一個數列$s$來說,如果存在正整數 $i,\;j$ 使得 $0 \leq i < j \leq n-1$ 而且 $s[i] \geq s[j]$,則 $(i,j)$ 這一個有序對稱為 $s$ 的一個SMM數對

現在給你一個長度為n的數列,請你求出SMM數對的總數

輸入說明

輸入有多比測資,第一行一個數字$n,\;0\leq n \leq 10^6$,表示詢問為$n$長度的數列,第二行有$n$個整數依序為數列的每一項,以一個空白隔開。當$n=-1$表示輸入結束,你不必對這筆資料作處理。

輸出說明

對於每組測試資料請先輸出這是第幾個數列,然後是該數列的SMM數對的總數。

詳請見範例輸入輸出

範例輸入

5
1 2 3 4 5
5
5 5 5 5 5
5
1 2 3 5 4
5
5 4 3 2 1
-1

範例輸出

Case #1: 0
Case #2: 10
Case #3: 1
Case #4: 10

配分方法

  • 10% $n \leq 100$
  • 20% $n \leq 1000$
  • 30% $n \leq 10^4$
  • 40% $n \leq 10^6$

Hints

可以把序列切成兩半,左邊右邊都算完再算橫跨兩邊的,遞迴下去做
或是你想用BIT(Binary Index Tree)好像可以做一些事情

備註

我會抓抄襲喔

Judge Setting

run-time limit: 200 ms
memory limit: 655360 byte
測資數量: 0