using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using YukicoderContest273.Extensions; using YukicoderContest273.Questions; namespace YukicoderContest273.Questions { public class QuestionD : AtCoderQuestionBase { public override IEnumerable Solve(TextReader inputStream) { var n = inputStream.ReadInt(); var a = inputStream.ReadIntArray(); var b = inputStream.ReadIntArray(); Array.Sort(a); var ab = new int[2 * n]; for (int i = 0; i < a.Length; i++) { ab[i] = a[i]; } for (int i = 0; i < b.Length; i++) { ab[n + i] = b[i]; } var comp = new CompressedCoordinate(ab); var bit = new BinaryIndexedTree(comp.Count); long result = 0; for (int i = 0; i < a.Length; i++) { bit[comp[n + i]]++; result += bit.Sum(comp[i]); } yield return result; } public class CompressedCoordinate where T : IComparable, IEquatable { readonly int[] _compressed; readonly T[] _expander; public int Count => _expander.Length; public CompressedCoordinate(T[] data) { _expander = data.ToArray().Distinct().ToArray(); Array.Sort(_expander); _compressed = new int[data.Length]; var span = _expander.AsSpan(); for (int i = 0; i < _compressed.Length; i++) { _compressed[i] = span.BinarySearch(data[i]); } } public int this[int index] => _compressed[index]; public T Expand(int compressedValue) => _expander[compressedValue]; } public class BinaryIndexedTree { long[] _data; public int Length { get; } public BinaryIndexedTree(int length) { _data = new long[length + 1]; // 内部的には1-indexedにする Length = length; } public BinaryIndexedTree(IEnumerable data, int length) : this(length) { var count = 0; foreach (var n in data) { AddAt(count++, n); } } public BinaryIndexedTree(ICollection collection) : this(collection, collection.Count) { } public long this[int index] { get => Sum(index, index + 1); set => AddAt(index, value - this[index]); } /// /// BITのindex番目の要素にnを加算します。 /// /// 加算するインデックス(0-indexed) /// 加算する数 public void AddAt(int i, long value) { unchecked { if ((uint)i >= (uint)Length) { throw new ArgumentOutOfRangeException(nameof(i)); } } i++; // 1-indexedにする while (i <= Length) { _data[i] += value; i += i & -i; // LSBの加算 } } /// /// [0, end)の部分和を返します。 /// /// 部分和を求める半開区間の終了インデックス /// 区間の部分和 public long Sum(int i) { unchecked { if ((uint)i >= (uint)_data.Length) { throw new ArgumentOutOfRangeException(nameof(i)); } } long sum = 0; while (i > 0) { sum += _data[i]; i -= i & -i; // LSBの減算 } return sum; } /// /// [start, end)の部分和を返します。 /// /// 部分和を求める半開区間の開始インデックス /// 部分和を求める半開区間の終了インデックス /// 区間の部分和 public long Sum(int start, int end) => Sum(end) - Sum(start); } } } namespace YukicoderContest273 { class Program { static void Main(string[] args) { IAtCoderQuestion question = new QuestionD(); var answers = question.Solve(Console.In); var writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(writer); foreach (var answer in answers) { Console.WriteLine(answer); } Console.Out.Flush(); } } } #region Base Class namespace YukicoderContest273.Questions { public interface IAtCoderQuestion { IEnumerable Solve(string input); IEnumerable Solve(TextReader inputStream); } public abstract class AtCoderQuestionBase : IAtCoderQuestion { public IEnumerable Solve(string input) { var stream = new MemoryStream(Encoding.Unicode.GetBytes(input)); var reader = new StreamReader(stream, Encoding.Unicode); return Solve(reader); } public abstract IEnumerable Solve(TextReader inputStream); } } #endregion #region Extensions namespace YukicoderContest273.Extensions { public static class StringExtensions { public static string Join(this IEnumerable source) => string.Concat(source); public static string Join(this IEnumerable source, char separator) => string.Join(separator, source); public static string Join(this IEnumerable source, string separator) => string.Join(separator, source); } public static class TextReaderExtensions { public static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader)); public static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader)); public static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader)); public static string ReadString(this TextReader reader) => reader.ReadLine(); public static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray(); public static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray(); public static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray(); public static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator); // Supports primitive type only. public static T1 ReadValue(this TextReader reader) => (T1)Convert.ChangeType(reader.ReadLine(), typeof(T1)); public static (T1, T2) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); return (v1, v2); } public static (T1, T2, T3) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); return (v1, v2, v3); } public static (T1, T2, T3, T4) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); return (v1, v2, v3, v4); } public static (T1, T2, T3, T4, T5) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); return (v1, v2, v3, v4, v5); } public static (T1, T2, T3, T4, T5, T6) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6)); return (v1, v2, v3, v4, v5, v6); } public static (T1, T2, T3, T4, T5, T6, T7) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6)); var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7)); return (v1, v2, v3, v4, v5, v6, v7); } public static (T1, T2, T3, T4, T5, T6, T7, T8) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6)); var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7)); var v8 = (T8)Convert.ChangeType(inputs[7], typeof(T8)); return (v1, v2, v3, v4, v5, v6, v7, v8); } } } #endregion