---
title: "AtCoder Beginner Contest 231 F(二維偏序)"
tags: 題解, 資料結構
---

https://atcoder.jp/contests/abc231/tasks/abc231_f

#### 題意

給 $N$ 個點 $(a_1, b_1), (a_2, b_2), ...$。求對於每個點 $(a_i, b_i)$，滿足 $a_j <= a_i$ 且 $b_j >= a_j$ 的點 $(a_j, b_j)$ 之個數。

#### 思路

二維偏序題，第二維逆著排序後、第一維順著排，確保該被處理的點要先被處理。
處理每個點的時候，先將點的第一維壓入樹狀數組，然後再從樹狀數組上得前綴和。由於等號成立時屬於合法的，所以對於相同第二維的點，要先全部壓入再逐一查詢。

#### Code

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    v2i, _ = compress(A)

    pts = defaultdict(list)
    for (a, b) in zip(A, B):
        pts[b].append(a)

    for b in pts.keys():
        pts[b].sort()

    ans = 0
    fenw = Fenwick(200005)
    for b in sorted(list(pts.keys()), reverse=True):
        for a in pts[b]: fenw.add(v2i[a], 1)
        for a in pts[b]: ans += fenw.pref(v2i[a] + 1)

    print(ans)

if __name__ == "__main__":
    solve()