#nullable enable using System.Numerics; #region var (_input, _iter) = (Array.Empty(), 0); string String() { while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Split(' '), 0); return _input[_iter++]; } T I() where T : IParsable => T.Parse(String(), null); #endregion static T[] Range(int n, Func F) => Enumerable.Range(0, n).Select(_ => F()).ToArray(); var n = I(); var mz = Range(n, () => (I(), I(), 1L)); var max = 1U << 20; long Solve(int l, int r) { if (r - l <= 32) { var res = 0L; for (var i = l; i < r; i++) { var (l1, r1, _) = mz[i]; for (var j = i + 1; j < r; j++) { var (l2, r2, _) = mz[j]; if (l1 < l2 && r2 < r1) res++; } } return res; } var mid = (l + r) >> 1; var v = 0L; v += Solve(l, mid); var k = mid - l; var points = new (uint, uint, long)[k]; for (var i = 0; i < k; i++) points[i] = mz[i + l]; var map = new PointMap(points); for (var i = mid; i < r; i++) { var (x, y, _) = mz[i]; v += map.Sum((0, y), (x, max)); } v += Solve(mid, r); return v; } var ans = Solve(0, n); Console.WriteLine(ans); class WaveletMatrix where T : IAdditionOperators, ISubtractionOperators, IAdditiveIdentity { const int d = 21; uint[,] Rank0 { get; init; } T[,] Sum { get; init; } int Length => Rank0.GetLength(1) - 1; public WaveletMatrix((uint, T)[] array) { var n = array.Length; var ranks = new uint[d, n + 1]; var sum = new T[d, n + 1]; var a = array.AsSpan(); var b = new (uint, T)[n].AsSpan(); var a0 = new (uint, T)[n].AsSpan(); var a1 = new (uint, T)[n].AsSpan(); for (var i = d - 1; i >= 0; i--) { var (i0, i1) = (0, 0); for (var j = 0; j < n; j++) { ranks[i, j + 1] += ranks[i, j]; var v = a[j]; if ((v.Item1 & (1U << i)) > 0) { ranks[i, j + 1]++; a1[i1++] = v; } else a0[i0++] = v; } for (var j = 0; j < i0; j++) b[j] = a0[j]; for (var j = 0; j < i1; j++) b[j + i0] = a1[j]; sum[i, 0] = T.AdditiveIdentity; for (var j = 0; j < n; j++) sum[i, j + 1] = sum[i, j] + b[j].Item2; var tmp = a; a = b; b = tmp; } for (var i = 0; i < d; i++) for (var j = 1U; j <= n; j++) ranks[i, j] = j - ranks[i, j]; (Rank0, Sum) = (ranks, sum); } public T Frequency(uint l, uint r, uint upper) // [l, r), [0, upper) { var (n, rank0, sum) = (Length, Rank0, Sum); var res = T.AdditiveIdentity; for (var i = d - 1; i >= 0; i--) { if (l >= r) break; var (l0, r0) = (rank0[i, l], rank0[i, r]); if ((upper & (1U << i)) > 0) { res += sum[i, r0] - sum[i, l0]; var zeros = rank0[i, n]; l += zeros - l0; r += zeros - r0; } else (l, r) = (l0, r0); } return res; } } class PointMap { readonly WaveletMatrix matrix; readonly uint[] xs; public PointMap((uint, uint, long)[] points) { var sorted = points.OrderBy(e => e.Item1); var xs = sorted.Select(e => e.Item1); var ys = sorted.Select(e => (e.Item2, e.Item3)); matrix = new WaveletMatrix(ys.ToArray()); this.xs = xs.ToArray(); } public long Sum((uint, uint) lowerLeft, (uint, uint) upperRight) // [lx, rx), [ly, ry) { var (lx, ly) = lowerLeft; var (rx, ry) = upperRight; if (lx > rx || ly > ry) return 0; return Sum(lx, ly, rx - lx, ry - ly); } public long Sum(uint x, uint y, uint dx, uint dy) // [x, x + dx), [y, y + dy) { var ux = uint.MaxValue; if (x <= ux - dx) ux = x + dx; var uy = uint.MaxValue; if (y <= uy - dy) uy = y + dy; var l = MinIndex(x); var r = MinIndex(ux); return matrix.Frequency(l, r, uy) - matrix.Frequency(l, r, y); } uint MinIndex(uint x) { var xs = this.xs; var (l, r) = (-1, xs.Length); while (r - l > 1) { var m = (l + r) >> 1; if (xs[m] < x) l = m; else r = m; } return (uint)r; } }