/* 解説ページにリンクのあったc-yanさんによるユーザ解説にあった手法 B[i]を逐次追加してソートして二分探索する ソートして二分探索する配列を2つに分ける 短い配列と長い配列とに 短い配列のほうにB[i]を挿入してはソート 短い配列と長い配列をA[i]で二分探索して個数を数える 短い配列がいっぱいになったら 長い配列に全部挿入して、長い配列をソート、短い配列を空にする 短い配列の長さを M とするなら 短い配列のソートを N 回実行するので 時間計算量は O( N * M * log(M) ) 長い配列のソートは N/M 回実行されるので 時間計算量は O( N/M * N * log(N) ) Mをうまくとるなら M = sqrt(N) とすると どちらのソートも計算量は O( sqrt(N) * N * log(N) ) になる 今回の問題の N の最大値と実行制限時間においては間に合うらしい これ O( sqrt(N) * N * log(N) ) が間に合うのなら 累積和を平方分割管理で処理しても間に合うのでは? 平方分割は間に合わないと思って除外して考えてたけど 試してみよう */ package main import . "fmt" import . "os" import bf "bufio" import . "slices" import "math" func main() { rd := bf.NewReader(Stdin) var n int Fscan(rd, &n) a := make([]int, n) for i := range a { Fscan(rd, &a[i]) } b := make([]int, n) for i := range b { Fscan(rd, &b[i]) } // 座標圧縮 // 今回は値そのものは答えに使用しないためインデックスに置き換えるだけ keys := Concat(a, b) Sort(keys) keys = Compact(keys) table := make(map[int]int) for i, k := range keys { table[k] = i } for i, k := range a { a[i] = table[k] } for i, k := range b { b[i] = table[k] } Sort(a) rootN := int(math.Ceil(math.Sqrt(float64(n)))) rootN = max(rootN, (n+rootN-1)/rootN) rootN = max(rootN, (n+rootN-1)/rootN) arr1 := make([]int, rootN+1) arr2 := make([][]int, rootN+1) for i := range arr2 { arr2[i] = make([]int, rootN+1) } ans := 0 for i := 0; i < n; i++ { p1 := b[i] / rootN for j := p1+1; j < len(arr1); j++ { arr1[j]++ } p2 := b[i] % rootN for j := p2+1; j < len(arr2[p1]); j++ { arr2[p1][j]++ } q1 := a[i] / rootN ans += arr1[q1] q2 := a[i] % rootN ans += arr2[q1][q2] } Println(ans) }