#include #include using namespace std; using mint = atcoder::modint1000000007; const int inf = (1 << 30) - 1; #line 1 "structure/others/abstract-binary-indexed-tree.cpp" /** * @brief Abstract Binary Indexed Tree(抽象化BIT) * @docs docs/abstract-binary-indexed-tree.md */ template< typename T, typename F > struct AbstractBinaryIndexedTree { private: int n; vector< T > data; const F f; const T e; public: AbstractBinaryIndexedTree() = default; explicit AbstractBinaryIndexedTree(int n, const F f, const T &e) : n(n), f(f), e(e) { data.assign(n + 1, e); } explicit AbstractBinaryIndexedTree(const vector< T > &v, const F f, const T &e) : AbstractBinaryIndexedTree((int) v.size(), f, e) { build(v); } void build(const vector< T > &v) { assert(n == (int) v.size()); for(int i = 1; i <= n; i++) data[i] = v[i - 1]; for(int i = 1; i <= n; i++) { int j = i + (i & -i); if(j <= n) data[j] = f(data[j], data[i]); } } void apply(int k, const T &x) { for(++k; k <= n; k += k & -k) data[k] = f(data[k], x); } T prod(int r) const { T ret{e}; for(; r > 0; r -= r & -r) ret = f(ret, data[r]); return ret; } }; template< typename T, typename F > AbstractBinaryIndexedTree< T, F > get_abstract_binary_indexed_tree(int n, const F &f, const T &e) { return AbstractBinaryIndexedTree{n, f, e}; } template< typename T, typename F > AbstractBinaryIndexedTree< T, F > get_abstract_binary_indexed_tree(const vector< T > &v, const F &f, const T &e) { return AbstractBinaryIndexedTree{v, f, e}; } #line 2 "structure/others/abstract-2d-binary-indexed-tree-compressed.cpp" /** * @brief Abstract 2D Binary Indexed Tree Compressed(抽象化2次元座圧BIT) */ template< typename T, typename F > struct Abstract2DBinaryIndexedTreeCompressed { private: int n; vector< AbstractBinaryIndexedTree< T, F > > data; const F f; const T e; vector< int > hs; vector< vector< int > > beet; public: Abstract2DBinaryIndexedTreeCompressed(const vector< int > &hs, const F f, const T &e) : n((int) hs.size()), hs(hs), f(f), e(e) { vector< int > ord(n); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), [&](int a, int b) { return hs[a] < hs[b]; }); beet.resize(n + 1); for(auto &&i: ord) { for(int k = i + 1; k <= n; k += k & -k) { beet[k].emplace_back(hs[i]); } } data.reserve(n + 1); for(int k = 0; k <= n; k++) { beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k])); data.emplace_back((int) beet[k].size(), f, e); } } void apply(int k1, const T &x) { int k2 = hs[k1]; for(++k1; k1 <= n; k1 += k1 & -k1) { int p = lower_bound(begin(beet[k1]), end(beet[k1]), k2) - begin(beet[k1]); data[k1].apply(p, x); } } T prod(int r1, int r2) const { T ret{e}; for(; r1 > 0; r1 -= r1 & -r1) { int p = lower_bound(begin(beet[r1]), end(beet[r1]), r2) - begin(beet[r1]); ret = f(ret, data[r1].prod(p)); } return ret; } }; template< typename T, typename F > Abstract2DBinaryIndexedTreeCompressed< T, F > get_abstract_2d_binary_indexed_tree_compressed(const vector< int > &hs, const F &f, const T &e) { return Abstract2DBinaryIndexedTreeCompressed{hs, f, e}; } mint solve(const vector< int > &A, const vector< int > &B) { int N = (int) A.size(); mint ret = 0; { vector< int > ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), [&](int a, int b) { return A[a] < A[b]; }); vector< pair< int, int > > pts(N); for(int i = 0; i < N; i++) pts[i] = {A[i] - B[i], A[i] + B[i]}; sort(begin(pts), end(pts)); pts.erase(unique(begin(pts), end(pts)), end(pts)); vector< int > xs(pts.size()), ys(pts.size()), ds(pts.size()); for(int i = 0; i < (int) pts.size(); i++) { tie(xs[i], ys[i]) = pts[i]; } auto bs = get_abstract_2d_binary_indexed_tree_compressed(ys, [](int a, int b) { return a + b; }, 0); for(int i: ord) { { int left = lower_bound(begin(xs), end(xs), A[i] - B[i]) - begin(xs); int right = (int) pts.size(); int pct = bs.prod(left, A[i] + B[i]); ret += mint(A[i]) * pct; } { int idx = lower_bound(begin(pts), end(pts), make_pair(A[i] - B[i], A[i] + B[i])) - begin(pts); bs.apply(idx, 1); } } } { vector< int > ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), [&](int a, int b) { return A[a] > A[b]; }); vector< pair< int, int > > pts(N); for(int i = 0; i < N; i++) pts[i] = {-(A[i] + B[i]), -(A[i] - B[i])}; sort(begin(pts), end(pts)); pts.erase(unique(begin(pts), end(pts)), end(pts)); vector< int > xs(pts.size()), ys(pts.size()), ds(pts.size()); for(int i = 0; i < (int) pts.size(); i++) { tie(xs[i], ys[i]) = pts[i]; } auto bs = get_abstract_2d_binary_indexed_tree_compressed(ys, [](int a, int b) { return a + b; }, 0); for(int i: ord) { { int left = lower_bound(begin(xs), end(xs), -(A[i] + B[i])) - begin(xs); int right = (int) pts.size(); int pct = bs.prod(left, -(A[i] - B[i])); ret -= mint(A[i]) * pct; } { int idx = lower_bound(begin(pts), end(pts), make_pair(-(A[i] + B[i]), -(A[i] - B[i]))) - begin(pts); bs.apply(idx, 1); } } } return ret * 2; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N; cin >> N; vector< int > A(N), B(N); for(auto &a: A) cin >> a; for(auto &b: B) cin >> b; cout << solve(A, B).val() << " " << solve(B, A).val() << "\n"; }