c066: RMQSUM$(RMQSUM)$
Tags :
Accepted rate : 1人/2人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-06-05 16:31

Content

先備知識:

RMQ Problem(Range Minimum/Maximum Query),區間最小/大值問題是一個很常見的問題。

簡單來說就是給定一個陣列A和Q個詢問,每次詢問A中某個區間的最大值/最小值。

這個問題使用線段樹可以達到預處理/詢問複雜度$O(N)/O(logN)$,而使用稀疏表可以達到$O(NlogN)/O(1)$。

 

給定一個陣列A,定義$RMQ(l,r)$表示$A[l,r]$中的最小值,請輸出

\[ \sum_{i=1}^{N}\sum_{j=i}^{N} RMQ(i,j) \]

Input

第一行為A的長度$N(N \leq 200000)$

第二行是A裡面的數字(絕對值 $\leq 10^5$)。

Output

\[ \sum_{i=1}^{N}\sum_{j=i}^{N} RMQ(i,j) \]

Sample Input
5
1 2 3 4 5
Sample Output
35
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
Hint :

子題一(40%):$N \leq 2000$

子題二(60%):無其他限制。

Tags:
出處:
[管理者:
810848 (路過)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」