package main import . "fmt" import . "os" import bf "bufio" import . "slices" 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]) } btree := newTree(Concat(a, b)) Sort(a) ans := 0 for i := 0; i < n; i++ { btree.add(b[i]) ans += btree.lowerCount(a[i]) } Println(ans) } /* 考察 累積和や統計の情報の取得や追加や更新が高速で行えるデータ構造やアルゴリズムを使って解く問題のように見える aは昇順に並びかえて BITや順序付きマップ(平衡二分探索木)などを使い i番目の操作にb[i]を追加して、a[i]未満の個数を取得する、の繰り返し Go言語の標準には実装されてないし BITや平衡二分探索木をそらでは実装できないし どちらも事前にコードを用意してないので(コンテストであれば不利) */ type Node struct { key, cnt, lc, uc int lower, upper *Node } func (n *Node)count() int { if n == nil { return 0 } return n.cnt+n.lc+n.uc } func newTree(keys []int) *Node { keys = Clone(keys) if !IsSorted(keys) { Sort(keys) } keys = Compact(keys) return build(keys) } func build(keys []int) *Node { if len(keys) == 0 { return nil } n := new(Node) if len(keys) == 1 { n.key = keys[0] return n } p := len(keys)/2 n.key= keys[p] n.lower = build(keys[:p]) n.upper = build(keys[p+1:]) return n } func (n *Node) add(key int) { switch { case n.key == key: n.cnt++ case n.key < key: n.uc++ n.upper.add(key) case n.key > key: n.lc++ n.lower.add(key) } } func (n *Node)lowerCount(key int) int { switch { case n.key == key: return n.lc case n.key < key: return n.cnt+n.lc+n.upper.lowerCount(key) case n.key > key: return n.lower.lowerCount(key) } // 賢いコンパイラとかだと不要になるreturn return 0 }