f315. 4. 低地距離
Tags : APCS 分治法 線段樹
Accepted rate : 759人/1130人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-10-24 15:24

Content

輸入一個長度為 $2n$ 的陣列,其中 $1$ ~ $n$ 的每個數字都剛好各 2 次。

$i$ 的低窪值的定義是兩個數值為 i 的位置中間,有幾個小於 i 的的數字。

以 $[3, 1, 2, 1, 3, 2] 為例,1的低窪值為 0, 2 的低窪值值為 1, 3 的低窪值為 3。

請對於每個 $1$ ~ $n$ 的數字都求其低窪值(兩個相同的數字之間有幾個數字比它小),輸出低窪值的總和,答案可能會超過 C++ int 的上限。

Input

第一行有一個正整數 $n$

第二行有 $2n$ 個正整數,以空格分隔,保證 $1~n$ 每個數字都恰好出現兩次。

 

配分

  • 20%: $1\leq n \leq 1000$
  • 40%: $1\leq n \leq 40000$
  • 40%: $1\leq n \leq 100000$

 

Output

輸出 $1$ ~ $n$ 每個數字的低窪值總和。

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

分治法

Tags:
APCS 分治法 線段樹
出處:
2020年10月APCS [管理者: cthbst (吳宗達) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
36664 fire5386 (becaidorz) f315
629 2023-07-31 21:10
34654 luray0601@gm ... (QWERTYPIG) f315
C++題解(含想法)
925 2023-04-05 16:49
34520 willy633526@ ... (ByTech) f315
python 題解
596 2023-03-26 22:33
27438 r1cky (hehe) f315
1709 2021-10-05 16:00
24925 fire5386 (becaidorz) f315
資料結構
2791 2021-04-05 18:18