/* 解説よんだ やはりBIT 座標圧縮が必要とあって それには気が付かなかった 問題のタグに二分探索とあって 解説にはそれについて触れられておらず ユーザ解説としてリンクされてた記事の方法もタグの意図とは違っていそうだったので 人々の提出コードを眺めて二分探索解法が判明した ポイントは『 B[i] は何回カウントされたか』 N = 6 で A をソート済みとして以下のようなケースを考える A = [ 1, 4, 7, 9, 14, 20] B = [ 3, 8, 2, 11, 5, 7] 例えば B[1] = 10 は何回カウントされるかというと A[3] = 9 と A[4] = 14 と A[5] = 20 の 3 回カウントされる これは A を B[1] = 10 の値で二分探索すればその位置以降の A[i] によってカウントされるので求めた位置以降の個数を数えればいい 例えば B[4] = 5 は何回カウントされるかというと A[4] = 14 と A[5] = 20 の 2 回カウントされる これは A を B[4] = 5 の値で二分探索すると A[2] = 7 の位置が求まるが実際にカウントされるのは B[4] と同じ位置の A[4] からとなる よって B[4] の位置と同じ位置以降の個数をカウントすればよい このやり方、以前にAtCoderかCodeforcesで見た気がする */ package main import . "fmt" import . "os" import bf "bufio" import . "sort" 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]) } Ints(a) ans := 0 for i := 0; i < n; i++ { p := Search(len(a), func(k int) bool { return a[k] > b[i] }) if p < i { ans += n - i } else { ans += n - p } } Println(ans) }