#include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) using namespace std; templatebool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; } templatebool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; } template inline int sz(T &a) { return a.size(); } using ll = long long; using ld = long double; using pi = pair; using pl = pair; using vi = vector; using vvi = vector; using vl = vector; using vvl = vector; const int inf = numeric_limits::max(); const ll infll = numeric_limits::max(); // 一次元座圧. // 同じ値は同じ値に圧縮される template class Compress{ public: vector a; // 元の配列 vector data; // 座圧後の配列 map mp; // key->元の配列の値, val->座圧後の値 void add(T val) { a.emplace_back(val); } void build() { vector vals = a; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); rep(i,sz(a)) { int id = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin(); // id + 1にすれば1-indexedになる mp[a[i]] = id; data.push_back(id); } } int a2data(T val) { return mp.lower_bound(val)->second; } void test() { vector v = {3, 3, 1, 6, 1}; for(auto val: v) add(val); build(); for(auto val: data) cout << val << " "; cout << "\n"; // 1 1 0 2 0 cout << a2data(2) << "\n"; // 1 } }; //---------------------------- // 抽象化セグ木 // 二項演算と単位元を渡して使ってね ///****例**************************** // auto f = [&](int a,int b){ return a+b;}; // 二項演算:和 // int id = 0; //単位元:0 // SegTree seg(f,id); //************************************ //---------------------------- template struct SegTree{ // 二項演算merge,単位元identify T identity; F merge; int size; vector dat; // 二項演算fと単位元idを渡して宣言する SegTree(F f,T id):merge(f),identity(id){} // データの要素の数nを渡して初期化、sizeはnより大きい2の冪乗 void init(int n){ size = 1; while(size<=n) size *= 2; dat.resize(size*2-1,identity); } // 配列を渡して0(n)で初期化 void build(vector vec){ rep(i,vec.size()) dat[size-1+i] = vec[i]; dfs(0); } T dfs(int k){ if(k>=size-1) return dat[k]; else return dat[k] = merge(dfs(2*k+1),dfs(2*k+2)); } // index kの要素をaに変更 void update(int k,T a){ k += size - 1; dat[k] = a; while(k > 0){ k = (k-1)/2; dat[k] = merge(dat[2*k+1],dat[2*k+2]); } } // index kの要素にaを加算 void add(int k,T a){ k += size - 1; dat[k] += a; while(k > 0){ k = (k-1)/2; dat[k] = merge(dat[2*k+1],dat[2*k+2]); } } // 区間[a,b)に対するクエリに答える。(k,l,r)=(0,0,size) T query(int a,int b,int k,int l,int r){ if(r<=a||b<=l) return identity; if(a<=l&&r<=b) return dat[k]; else return merge(query(a,b,2*k+1,l,(l+r)/2),query(a,b,2*k+2,(l+r)/2,r)); } T query(int a,int b){ return query(a, b, 0, 0, size); } // デバッグ用 void show(){ int index = 0; int num = 1; while(index> n; vi a(n),b(n); rep(i,n) cin >> a[i]; rep(i,n) cin >> b[i]; sort(a.begin(), a.end()); Compress cp; rep(i,n) cp.add(a[i]); rep(i,n) cp.add(b[i]); cp.build(); rep(i,n) a[i] = cp.data[i]; rep(i,n) b[i] = cp.data[i+n]; auto f = [&](ll a,ll b){ return a+b;}; // 二項演算:和 ll id = 0; //単位元:0 SegTree seg(f,id); seg.init(2*n); ll sum = 0; rep(i,n) { seg.add(b[i], 1); sum += seg.query(0, a[i]); } cout << sum << "\n"; return 0; }