Code for my competitive programming talk in C++ and Javascript. It solves the "Mega Inversion" problem from NCPC 2011: http://ncpc.idi.ntnu.no/ncpc2011/ncpc2011problems.pdf

fast.cpp

#include<iostream>
#include<vector>
using namespace std;

typedef long long ll;

ll n;
vector<int> numbers;

struct Tree {
  vector<ll> tree;

  Tree(ll size)
  {
    tree.assign(size * 4, 0);
  }

  ll left_memory(ll position)
  {
    return position * 2;
  }

  ll right_memory(ll position)
  {
    return position * 2 + 1;
  }

  void add(ll position, ll start, ll end, ll key, ll value) 
  {
    if(start <= key && key <= end) {
      tree[position] += value;

      if(end > start) {
        add(left_memory(position), start, (start + end)/2, key, value);
        add(right_memory(position), (start + end)/2+1, end, key, value);
      }
    }
  }

  void add(ll key, ll value)
  {
    add(1,1,n,key,value);
  }

  ll sum(ll position, ll start, ll end, ll query_start, ll query_end)
  {
    if(query_start <= start && end <= query_end) {
      return tree[position];
    } else if(query_start > end || query_end < start) { 
      return 0;
    } else {
      return sum(left_memory(position), start, (start+end)/2, query_start, query_end) + 
        sum(right_memory(position), (start+end)/2+1,      end, query_start, query_end);
    }
  }

  ll sum(ll query_start, ll query_end) 
  {
    return sum(1,1,n,query_start,query_end);
  }
};

int main()
{
  scanf("%lld", &n);
  Tree frequency(n);
  Tree sum(n);

  numbers.resize(n);

  for(ll i = n - 1; i != -1; --i)
    scanf("%d", &numbers[i]);

  ll res = 0;
  for(ll i = 0; i < n; ++i) {
    frequency.add(numbers[i], 1);
    ll n_smaller = frequency.sum(1, numbers[i] - 1);
    // printf("Smaller than %d: %d\n", numbers[i], n_smaller);

    sum.add(numbers[i], n_smaller);
    ll sum_smaller = sum.sum(1, numbers[i] - 1);
    res += sum_smaller;
    // printf("Sum to %d: %d\n", numbers[i], sum_smaller);
  }

  printf("%lld\n", res);
}

fast.js

fs = require('fs');

function SegmentTree(n) {
  this.tree = [];

  for(var i = 0; i < n * 4; i++)
    this.tree.push(0);
}

SegmentTree.prototype.add = function(pos, start, end, key, value) {
  if(key <= end && key >= start) {
    this.tree[pos] += value;

    if(start != end) {
      this.add(pos * 2, start, Math.floor((start+end)/2), key, value);
      this.add(pos * 2 + 1, Math.floor((start+end)/2) + 1, end, key, value);
    }
  }
}

SegmentTree.prototype.query = function(pos, start, end, query_start, query_end) {
  if(start >= query_start && end <= query_end) {
    return this.tree[pos];
  } else if(end < query_start || start > query_end) {
    return 0;
  } else {
    return this.query(pos * 2, start, Math.floor((start+end)/2), query_start, query_end) +
      this.query(pos * 2 + 1, Math.floor((start+end)/2) + 1, end, query_start, query_end);
  }
}

fs.readFile("input.gen", "UTF-8", function(err, data) {
  var numbers = data.trim().split(" ").map(function(i) { return parseInt(i) })
  numbers.shift();

  numbers = numbers.reverse();

  var n = numbers.length;

  var frequency = new SegmentTree(n);
  var sum = new SegmentTree(n);

  var res = 0;

  for(var i = 0; i < n; i++) {
    frequency.add(1,1,n, numbers[i], 1);
    var smaller = frequency.query(1,1,n, 1, numbers[i] - 1);

    sum.add(1,1,n, numbers[i], smaller);
    var triplets = sum.query(1,1,n, 1,numbers[i] - 1);

    res += triplets;
  }

  console.log(res);
});

input.rb

n = ARGV[0]

File.open("input.gen", "w") do |f|
  f.write "#{n} "

  n.to_i.times do
    f.write "#{(rand(n.to_i - 1) + 1)} "
  end
end

slow.js

fs = require('fs');
fs.readFile("input.gen", "UTF-8", function(err, data) {
  var numbers = data.trim().split(" ").map(function(i) { return parseInt(i) })
  numbers.shift();

  var n = numbers.length;
  var res = 0;

  for(var i = 0; i < n; i++)
    for(var j = i + 1; j < n; j++)
      for(var k = j + 1; k < n; k++)
        if(numbers[i] > numbers[j] && numbers[j] > numbers[k]) res++;

  console.log(res);
});