PhuongVN's blog

Number of larger intergers

By PhuongVN, history, 5 months ago, In English

You are given an array of N integers With each integer a[I], call x is the number of integers before I and larger than a[I] Your task is find the sum of all x

If you know the solution, please give me some ideas about how to implement it. I have just started learning Segment Tree

  • Vote: I like it
  • -13
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You don't need segment trees for this. Here is my solution:

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long

template<typename T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void solve(){
    int n;
    cin>>n;
    ll sum=0,x;
    oset<ll> st;
    for(int i=0;i<n;i++){
        cin>>x;
        st.insert(-x);
        sum+=st.order_of_key(-x);
    }
    cout<<sum<<'\n';
}
 
int main(){
    solve();
    return 0;
}
→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    isn't this the same as counting inversions?

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah,u can use mergesort trees as well for this...

      → Reply
      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i understand the general idea, insert it into a set and find the iterator pointing to it. however, I don't get how you use the oset, template... can you explain how to manually code the order_of_key() function, if you can?

        → Reply
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, I never looked into the source code for this, but if u simply want to use basic functionalities only, use the MergeSort tree methods from geeksforgeeks.

          → Reply
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          it's a red-black tree, a whole balancing binary tree that uses case forking as the main operator, that order of key function is something which uses a lot of pointer etc you can't just implement it randomly, you can either code the whole data structure or use merge sort:

          #include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn = 1e5+20;

ll ans = 0;

vector<ll> merge(vector<ll> c, vector<ll> b){
  vector<ll> res;
  ll i = 0, j = 0;
  while (i < c.size() && j < b.size()){
    if (c[i] > b[j]) res.pb(c[i]), i++;
    else ans+= (c.size() - i), res.pb(b[j]), j++;
  }
  for (int u = i ; u < c.size() ; u ++) res.pb(c[u]);
  for (int u = j ; u < b.size() ; u ++) res.pb(b[u]);
 
  return res;
}
 
vector<ll> mergeSort(vector<ll> b){
  vector<ll> c, d;
  if (b.size() == 1) return b;
  for (int i = 0 ; i < b.size() / 2 ; i ++) c.pb(b[i]);
  for (int i = b.size() / 2 ; i < b.size() ; i ++) d.pb(b[i]);
  return merge(mergeSort(c), mergeSort(d));
}


void run() {
  ll n; cin >> n, ans = 0;
  vector<ll> a(n);
  for (int i = 0 ; i < n ; i ++) cin >> a[i];
  mergeSort(a);
  cout << ans << nl;
}

          There is also a way to count inversions using a segment tree, idk it

          → Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this won't work for duplicate occurances

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
      template<typename T> using oset=tree<T, null_type, greater<T>, rb_tree_tag, tree_order_statistics_node_update>;

void solve(){
    int n;
    cin>>n;
    ll sum=0,x;
    oset<pair<ll, ll>> st;
    for(ll i=0;i<n;i++){
        cin>>x;
        st.insert({x, i});
        sum+=st.order_of_key({x, 0});
    }
    cout<<sum<<'\n';
}
      → Reply
      • »
        »
        »
        »
        5 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        nice, this'll work (but u need to insert {-x, i})

        → Reply
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I changed the oset definition to use greater instead of less

          → Reply