Why Did the Cow Cross The Road III

#include <cstdio>
#include <iostream>
#include <map>
#include <vector>
 
using std::vector;
 
// BeginCodeSnip{Segment Tree Implementation}
template <class T> struct Seg {
	int n;
	const T ID = 0;
	vector<T> seg;
 
	T comb(T a, T b) { return a + b; }
 
	void init(int _n) {
		n = _n;
		seg.assign(2 * n, ID);
	}
 
	void pull(int p) { seg[p] = comb(seg[2 * p], seg[2 * p + 1]); }
 
	// actualizar el valor en la posición p
	void upd(int p, T val) {
		seg[p += n] = val;
 
		for (p /= 2; p; p /= 2) { pull(p); }
	}
 
	// obtener la suma en el intervalo [l, r]
	T query(int l, int r) {
		T ra = ID, rb = ID;
		for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
			if (l & 1) ra = comb(ra, seg[l++]);
			if (r & 1) rb = comb(seg[--r], rb);
		}
		return comb(ra, rb);
	}
};
// EndCodeSnip
 
int main() {
	freopen("circlecross.in", "r", stdin);
	freopen("circlecross.out", "w", stdout);
 
	int n;
	std::cin >> n;
 
	vector<int> loc(2 * n);
 
	for (int i = 0; i < 2 * n; i++) {
		int cow_id;
		std::cin >> cow_id;
 
		// indexar las vacas desde cero
		loc[i] = --cow_id;
	}
 
	Seg<int> start_occ;
	start_occ.init(2 * n);
 
	int crossing_pairs = 0;
	std::map<int, int> starts;
 
	for (int i = 0; i < 2 * n; i++) {
		// si esta vaca aún no empezó
		if (starts.find(loc[i]) == starts.end()) {
			// registrar su ubicación
			starts[loc[i]] = i;
			start_occ.upd(i, 1);
			// esta vaca está terminando
		} else {
			// sumar la cantidad de vacas que empezaron dentro de este rango
			crossing_pairs += start_occ.query(starts[loc[i]] + 1, i - 1);
 
			// reiniciar el estado de la vaca
			start_occ.upd(starts[loc[i]], 0);
			starts.erase(loc[i]);
		}
	}
 
	std::cout << crossing_pairs << std::endl;
}

import java.io.*;
import java.util.*;
 
public class CircleCross {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(new File("circlecross.in"));
		PrintWriter out = new PrintWriter("circlecross.out");
 
		int n = sc.nextInt();
		int[] points = new int[n * 2];
		for (int i = 0; i < n * 2; i++) { points[i] = sc.nextInt() - 1; }
 
		// definimos un punto de entrada como "activo" si ya fue procesado, pero
		// su punto de salida correspondiente aún no fue procesado
 
		// seg[i] == 1 si i es un punto de entrada activo
		SegmentTree seg = new SegmentTree(n * 2);
		// almacena puntos de entrada activos, mapea cowId -> ubicación del punto de entrada
		Map<Integer, Integer> active = new HashMap<>();
		int ans = 0;
		// iterar por cada punto
		for (int i = 0; i < n * 2; i++) {
			// el punto es un punto de entrada
			if (!active.containsKey(points[i])) {
				// activar el punto de entrada
				seg.add(i, 1);
				active.put(points[i], i);
			}
			// el punto es un punto de salida
			else {
				/*
				 * incrementar ans por la cantidad de puntos de entrada activos
				 * entre los puntos de entrada y salida de la vaca - la vaca
				 * formará puntos de cruce con esas vacas
				 */
				ans += seg.sum(active.get(points[i]) + 1, i - 1);
 
				// el punto de entrada de la vaca ya no está activo, desactivarlo
				seg.add(active.get(points[i]), -1);
				active.remove(points[i]);
			}
		}
		out.println(ans);
		out.close();
	}
 
	static class SegmentTree {
		private int[] tree;
		private int n;
 
		public SegmentTree(int n) {
			this.n = n;
			tree = new int[n * 2];
		}
 
		public int sum(int a, int b) {
			a += n;
			b += n;
			int sum = 0;
			while (a <= b) {
				if (a % 2 == 1) sum += tree[a++];
				if (b % 2 == 0) sum += tree[b--];
				a /= 2;
				b /= 2;
			}
			return sum;
		}
 
		public void add(int index, int amount) {
			index += n;
			tree[index] += amount;
			for (index /= 2; index >= 1; index /= 2) {
				tree[index] = tree[2 * index] + tree[2 * index + 1];
			}
		}
	}
}