TRIPLETS from InterviewStreet

gistfile1.cs

using System;
using System.Collections.Generic;
using System.Linq;

interface ISparseSortedArray {
  void Set(uint position, ulong value);
	ulong Sum(ulong upperBound);
}

class TreapItem {
	public uint Key;
	public int Priority;
	public ulong Value;
	public ulong Sum;
	public TreapItem Left;
	public TreapItem Right;
}

static class Treap {
	public static bool FixExistingValue(TreapItem root, uint key, ulong value) {
		return FixExistingValueWithDelta(root, key, value).Item1;
	}

	public static TreapItem Insert(TreapItem root, uint key, ulong value) {
		Tuple<TreapItem, TreapItem> splitted = Split(root, key);
		var newItem = new TreapItem {
			Key = key,
			Priority = rnd.Next(),
			Value = value,
			Sum = value,
		};
		return Merge(Merge(splitted.Item1, newItem), splitted.Item2);
	}

	public static TreapItem Delete(TreapItem root, uint key) {
		if (root == null) {
			return null;
		}
		if (key == root.Key) {
			return Merge(root.Left, root.Right);
		}
		root.Left = Delete(root.Left, key);
		root.Right = Delete(root.Right, key);
		UpdateSum(root);
		return root;
	}

	public static ulong GetSum(TreapItem root) {
		return root == null ? 0 : root.Sum;
	}

	public static Tuple<bool, ulong> FixExistingValueWithDelta(TreapItem root, uint key, ulong value) {
		if (root == null) {
			return Tuple.Create(false, 0UL);
		}
		Tuple<bool, ulong> result = null;
		if (root.Key == key) {
			if (value < root.Value) {
				throw new Exception(string.Format("Tried to replace ({0}, {1}) with ({0}, {2})", key, root.Value, value));
			}
			result = Tuple.Create(true, value - root.Value);
			root.Value = value;
		} else {
			result = FixExistingValueWithDelta(root.Key < key ? root.Right : root.Left, key, value);
		}
		if (result.Item1) {
			root.Sum += result.Item2;
		}
		return result;
	}

	private static void UpdateSum(TreapItem root) {
		if (root != null) {
			root.Sum = root.Value + GetSum(root.Left) + GetSum(root.Right);
		}
	}

	private static Tuple<TreapItem, TreapItem> Split(TreapItem root, uint key) {
		if (root == null) {
			return new Tuple<TreapItem, TreapItem>(null, null);
		}
		TreapItem left = null;
		TreapItem right = null;
		if (root.Key <= key) {
			var splitted = Split(root.Right, key);
			root.Right = splitted.Item1;
			left = root;
			right = splitted.Item2;
		} else {
			var splitted = Split(root.Left, key);
			root.Left = splitted.Item2;
			left = splitted.Item1;
			right = root;
		}
		UpdateSum(left);
		UpdateSum(right);
		return Tuple.Create(left, right);
	}

	private static TreapItem Merge(TreapItem left, TreapItem right) {
		if (left == null) {
			return right;
		}
		if (right == null) {
			return left;
		}
		TreapItem result = null;
		if (right.Priority >= left.Priority) {
			left.Right = Merge(left.Right, right);
			result = left;
		} else {
			right.Left = Merge(left, right.Left);
			result = right;
		}
		UpdateSum(result);
		return result;
	}

	private static Random rnd = new Random();
}

class TreapSparseSortedArray : ISparseSortedArray {
	public void Set(uint position, ulong value) {
		if (!Treap.FixExistingValue(root, position, value)) {
			root = Treap.Insert(root, position, value);
		}
	}

	public ulong Sum(ulong upperBound) {
		return RecursiveSum(root, upperBound);
	}

	private ulong RecursiveSum(TreapItem root, ulong upperBound) {
		if (root == null) {
			return 0;
		}
		if (root.Key >= upperBound) {
			return RecursiveSum(root.Left, upperBound);
		} else {
			return root.Value + Treap.GetSum(root.Left) + RecursiveSum(root.Right, upperBound);
		}
	}

	private TreapItem root;
}

class DictionarySparseSortedArray : ISparseSortedArray {
	public void Set(uint position, ulong value) {
		d[position] = value;
	}

	public ulong Sum(ulong upperBound) {
		ulong sum = 0;
		foreach (var kvp in d) {
			if (kvp.Key >= upperBound) {
				break;
			}
			sum += kvp.Value;
		}
		return sum;
	}

	private SortedDictionary<uint, ulong> d = new SortedDictionary<uint, ulong>();
}

class Program {
	private static void Main() {
		var n = uint.Parse(Console.ReadLine());
		var numbers = Console.ReadLine().Split(new[]{' '}, StringSplitOptions.RemoveEmptyEntries).Select(uint.Parse).ToArray();

		var values = new ulong[n];
		for (var i = 0; i < values.Length; i++) {
			values[i] = 1;
		}

		ISparseSortedArray cumSum = null;
		for (var iter = 0; iter < 2; iter++) {
			cumSum = new TreapSparseSortedArray();
			for (var i = 0; i < values.Length; i++) {
				cumSum.Set(numbers[i], values[i]);
				values[i] = cumSum.Sum(numbers[i]);
			}
		}

		var seen = new HashSet<ulong>();
		ulong sum = 0;
		for (var i = values.Length - 1; i >= 0; i--) {
			if (!seen.Contains(numbers[i])) {
				seen.Add(numbers[i]);
				sum += values[i];
			}
		}
		Console.WriteLine(sum);
	}
}