#define PROBLEM "https://yukicoder.me/problems/no/1282" #include #include #include #include #include #include #include class CoordinateCompression { const std::vector m_v; const std::vector m_itox; const std::unordered_map m_xtoi; static inline auto c_itox(const std::vector& v) { auto itox = v; std::sort(itox.begin(), itox.end()); itox.erase(std::unique(itox.begin(), itox.end()), itox.end()); return itox; } static inline auto c_xtoi(const std::vector& itox) { std::unordered_map xtoi; for(unsigned int i = 0; i < itox.size(); ++i) { xtoi.emplace(itox[i], i); } return xtoi; } public: CoordinateCompression(const std::vector& v) : m_v(v), m_itox(c_itox(v)), m_xtoi(c_xtoi(m_itox)) { } auto size()const { return m_itox.size(); } auto toi(long long x)const { return m_xtoi.at(x); } auto tox(int i)const { return m_itox[i]; } auto c(const std::vector& v)const { std::vector ret; ret.reserve(size()); for(const auto& x : v) { ret.emplace_back(toi(x)); } return ret; } auto c()const { return c(m_v); } }; template class isMonoid { template static auto check(U x) -> decltype(x.binaryOperation(x), std::true_type{}); static std::false_type check(...); public: static bool const value = decltype(check(std::declval()))::value; }; template::value, std::nullptr_t> = nullptr > class SegmentTree { private: const int m_size; std::vector m_node; using S = decltype(Monoid().m_val); int calcSize(int n) const { int size = 1; while(size < n) { size <<= 1; }return size; } template auto _update_op(int itr, Monoid&& val, const Lambda& op) { int i = itr + m_size - 1; m_node[i] = op(m_node[i], std::forward(val)); while(i) { i = (i - 1) >> 1; m_node[i] = m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1]); } } auto _query(int _l, int _r) const { _l = std::max(_l, 0); _r = std::min(_r, m_size - 1); auto l = _l + m_size; int r = _r + m_size; auto lm = Monoid(); auto rm = Monoid(); while(l <= r) { if(l & 1) { lm = lm.binaryOperation(m_node[l - 1]); ++l; } if(!(r & 1)) { rm = m_node[r - 1].binaryOperation(rm); --r; } l >>= 1, r >>= 1; } return lm.binaryOperation(rm); } auto _construct(const std::vector& vec) { for(unsigned int i = 0; i < vec.size(); ++i) { m_node[i + m_size - 1] = Monoid(vec[i]); } for(int i = m_size - 2; i >= 0; --i) { m_node[i] = m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1]); } } public: SegmentTree(int n) : m_size(calcSize(n)), m_node((m_size << 1) - 1) {} SegmentTree(int n, const std::vector& vec) :SegmentTree(n) { _construct(vec); } template auto update_op(int itr, Monoid&& val, const Lambda& op) { return _update_op(itr, std::forward(val), op); } auto update(int itr, Monoid&& val) { return update_op(itr, std::forward(val), [](const Monoid&, const Monoid& m2) {return m2; }); } auto add(int itr, Monoid&& val) { return update_op(itr, std::forward(val), [](const Monoid& m1, const Monoid& m2) {return Monoid(m1.m_val + m2.m_val); }); } auto query(int l, int r)const { return _query(l, r).m_val; } auto query_all()const { return m_node[0].m_val; } auto output()const { for(int i = 0; i < m_size; ++i) { std::cout << m_node[m_size + i - 1] << " "; } std::cout << std::endl; } }; template< class S, // 要素の型 S element, // 元 class T // lambdaはC++20じゃないと渡せなかった... // S T(S, S) // 2項演算子 > struct Monoid { S m_val; Monoid() :m_val(element) {} Monoid(S val) :m_val(val) {} Monoid binaryOperation(const Monoid& m2)const { return T()(m_val, m2.m_val); } friend std::ostream& operator<<(std::ostream& os, const Monoid& m) { return os << m.m_val; } }; using ll = long long; using std::cout; using std::cin; constexpr char endl = '\n'; struct Functor { auto operator()(ll a, ll b)const { return a + b; } }; using M = Monoid; signed main() { ll n; cin >> n; std::vector a, b; a.reserve(n); b.reserve(n); for(int i = 0; i < n; ++i) { ll x; cin >> x; a.emplace_back(x); } for(int i = 0; i < n; ++i) { ll x; cin >> x; b.emplace_back(x); } std::sort(a.begin(), a.end()); auto ab = a; for(const auto& x : b) { ab.emplace_back(x); } auto cc = CoordinateCompression(ab); ll ans = 0; auto segtree = SegmentTree(cc.size()); for(int i = 0; i < n; ++i) { segtree.add(cc.toi(b[i]), 1); ans += segtree.query(0, cc.toi(a[i]) - 1); } cout << ans << endl; }